Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $.
\newline
Les conditions nécessaires pour que $ x^\ast \in \mathcal{C}$ soit un minimum local de $ J $ sont :
- \newline
- \newline
- \centerline{$ \{ \nabla g_1(x^\ast),\ldots,\nabla g_p(x^\ast),\nabla h_1(x^\ast),\ldots,\nabla h_q(x^\ast) \} $ sont linéairement indépendants.}
- \newline
- \newline
+ \begin{center}
+ $ \{ \nabla g_1(x^\ast),\ldots,\nabla g_p(x^\ast),\nabla h_1(x^\ast),\ldots,\nabla h_q(x^\ast) \} $ sont linéairement indépendants.
+ \end{center}
et
- $$ \forall i \in I \ \exists \mu_i \in \mathbb{R}_{+} \land \forall j \in J \ \exists \lambda_j \in \mathbb{R} \ \nabla J(x^\ast) + \sum_{i \in I}\mu_i{\nabla g_i(x^\ast)} + \sum_{j \in J}\lambda_j{\nabla h_j(x^\ast)} = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $$
+ \begin{center}
+ $ \forall i \in I \ \exists \mu_i \in \mathbb{R}_{+} \land \forall j \in J \ \exists \lambda_j \in \mathbb{R} $ tels que :
+ \end{center}
+ \begin{center}
+ $ \nabla J(x^\ast) + \sum\limits_{i \in I}\mu_i{\nabla g_i(x^\ast)} + \sum\limits_{j \in J}\lambda_j{\nabla h_j(x^\ast)} = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $
+ \end{center}
+ \begin{center}
+ $ \iff \nabla L(x^\ast,\lambda,\mu) = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $ où $ \lambda = (\lambda_1,\ldots,\lambda_q) $ et $ \mu = (\mu_1,\ldots,\mu_p) $.
+ \end{center}
On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
\newline
On nomme également les conditions \textit{KTT} conditions nécessaires d'optimalité du premier ordre.
\hrulefill
\newline
-ALGORITHME DE DESCENTE MODÈLE.
+ALGORITHME DE DESCENTE GÉNÉRIQUE.
\newline
\textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire.
\newline
\subsection{Critère d’arrêt}
-Soit $ x^\ast $ un minimum local de l'objectif $ J $ à optimiser. Supposons que l’on choisisse comme test d’arrêt dans l’algorithme de descente modèle, le critère idéal : "$ x_k = x^\ast $". Dans un monde idéal (i.e. en supposant tous les calculs exacts et la capacité de calcul illimitée), soit l’algorithme s’arrête après un nombre fini d’itérations, soit il construit (théoriquement) une suite infinie $ x_0,x_1,\ldots,x_k,\ldots $ de points de $ \mathbb{R}^n $ qui converge vers $ x^\ast $.
+Soit $ x^\ast $ un minimum local de l'objectif $ J $ à optimiser. Supposons que l’on choisisse comme test d’arrêt dans l’algorithme de descente générique, le critère idéal : "$ x_k = x^\ast $". Dans un monde idéal (i.e. en supposant tous les calculs exacts et la capacité de calcul illimitée), soit l’algorithme s’arrête après un nombre fini d’itérations, soit il construit (théoriquement) une suite infinie $ x_0,x_1,\ldots,x_k,\ldots $ de points de $ \mathbb{R}^n $ qui converge vers $ x^\ast $.
\newline
En pratique, un test d’arrêt devra être choisi pour garantir que l’algorithme s’arrête toujours après un nombre fini d’itérations et que le dernier point calculé soit suffisamment proche de $ x^\ast $.
\hline
& le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $. \\
\hline
- & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la hessienne est singulière. \\
+ & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la hessienne est singulière. \\
\hline
& pas de distinction entre minima, maxima et points stationnaires. \\
\hline
\subsection{Algorithmes Newtoniens}
-Les algorithmes newtoniens sont basés sur la linéarisation d’équations caractérisant les solutions que l’on cherche, fournies par les conditions d’optimalité d’ordre $ 1 $. Ces algorithmes sont \textit{primaux-duaux} dans le sens où ils génèrent à la fois une suite primale $ (x_k )_{k \in \mathbb{N}} $ convergeant vers une solution $ \overline{x} $ du problème considéré, et une suite duale $ (\lambda_k)_{k \in \mathbb{N}} $ (resp. $ ((\lambda_k, \mu_k))_{k \in \mathbb{N}} $) de multiplicateurs convergeant vers un multiplicateur optimal $ \overline{\lambda} $ (resp. $ (\overline{\lambda},\overline{\mu})) $ associé à $ \overline{x} $.
+Les algorithmes newtoniens sont basés sur la linéarisation d’équations caractérisant les solutions que l’on cherche, fournies par les conditions d’optimalité d’ordre $ 1 $. Ces algorithmes sont \textit{primaux-duaux} dans le sens où ils génèrent à la fois une suite primale $ (x_k )_{k \in \mathbb{N}} $ convergeant vers une solution $ \overline{x} $ du problème considéré, et une suite duale $ (\lambda_k)_{k \in \mathbb{N}} $ (resp. $ ((\lambda_k, \mu_k))_{k \in \mathbb{N}} $) de multiplicateurs convergeant vers un multiplicateur optimal $ \overline{\lambda} $ (resp. $ (\overline{\lambda},\overline{\mu}) $) associé à $ \overline{x} $.
\subsection{Algorithme PQS}
\hrulefill
\newline
-ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INEGALITÉ.
+ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ.
\newline
\textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $, $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$, $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ différentiables, $ x_0 \in \mathbb{R}^n $ point initial arbitraire, $ \lambda_0 \in \mathbb{R}_+^p $ et $ \mu_0 \in \mathbb{R}_+^q $ multiplicateurs initiaux, $ \varepsilon > 0 $ précision demandée.
\newline
\mathcal{PQ}_k \left \{
\begin{array}{l}
\displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
- g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0 \\, \ \forall j \in \{1,\ldots,p\} \\
+ g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\} \\
h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
\end{array}
\right .
\end{array}
\right .
$$
-où $$ (r,r_1,r_2) \in \mathbb{R}_+^3. $$
+où $$ (r,r_1,r_2) \in \mathbb{R}_+^{*^3} \land r < r_1 \land r < r_2. $$
\textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $ la précision, $ (x_0,y_0,z_0) = $ point initial et $ (\lambda_{0_1},\lambda_{0_2}) = $ multiplicateur initial.
\newline
Le Lagrangien $ L $ de $ \mathcal{P} $ : $$ L((x,y,z),(\lambda_1,\lambda_2)) = x^2 + y^2 + z^2 -r^2 + \lambda_1(x^2 + y^2 - r_1^2) + \lambda_2(x^2 + z^2 -r_2^2). $$
\end{pmatrix} = 2Id_{\mathbb{R}^3} $$
On en déduit que $ H[J](x,y,z) $ est inversible et que $ H[J](x,y,z)^{-1} = \frac{1}{2}Id_{\mathbb{R}^3} $.
- \subsection{Trace d'éxécution de l'algorithme PQS}
-\hrulefill
+ \newpage
- En utilisant le problème $ \mathcal{P} $ précédent :
- \newline
- \textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $, $ (x_0,y_0,z_0) = (80, 20, 60)$ et $(\lambda_{0_1},\lambda_{0_2}) = (1, 1)$, les rayons : $r = 40$ et $r_1 = r_2 = 10$.
- \newline
- Calcul du Lagrangien $ L $ de $ \mathcal{P} $ en $ (x_0,y_0,z_0)$ :
- \newline
- $ L((80,20,60),(1,1)) = 80^2 + 20^2 + 60^2 -60^2 + 1 * (80^2 +20y^2 - 30^2) + \lambda_2(80^2 + 60^2 -30^2), $
- \newline
- $ L((80,20,60),(1,1)) = 6400 + 400 + 3600 - 3600 + (6400 + 400 - 900) + (6400 + 3600 -900), $
- \newline
- $ L((80,20,60),(1,1)) = 21800. $
+ \subsection{Trace d'éxécution de PQS avec contrainte}
+ %\includegraphics[scale=0.2]{figure_sphere_avec_contrainte.png}\\
+ \begin{center}
+ \includegraphics[scale=0.2]{sphere2.jpg}\\
- \begin{algorithm}
- \caption {Algorithme PQS pour $ \mathcal{P} $}
- \begin{algorithmic}
- \REQUIRE $\varepsilon = 0.01$, $g(x,y,z)\leq 0$, $(x_0,y_0,z_0) = (80, 20 ,60)$, $(\lambda_{0_1},\lambda_{0_2}) = (1, 1)$, $r = 40$ et $r_1 = r_2 = 10$.
- \ENSURE $\displaystyle\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2$ and \newline
- $g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 $
+ \footnotesize{
+ \small \it Fig : Exemple de la sphère\\
+ \vspace*{0.5cm}
+ }
+ \end{center}
- \STATE \textbf{Data :}
- \STATE $k \leftarrow 0$
- \STATE $(x_k,y_k,z_k) \leftarrow (80,20,60)$
- \STATE $ H[J](x,y,z)^{-1} \leftarrow
- \begin{pmatrix}
- 0.5 & 0 & 0 \\
- 0 & 0.5 & 0 \\
- 0 & 0 & 0.5 \\
- \end{pmatrix} $
+ Utilisons le problème $ \mathcal{P} $ précédent :
- \WHILE{($\norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon$ or $k < 10$)}
+ $$
+ \mathcal{P} \left \{
+ \begin{array}{l}
+ \displaystyle\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2 \\
+ g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 \\
+ \end{array}
+ \right .
+ $$
+ où $$ (r,r_1,r_2) \in \mathbb{R}_+^3. $$
+ \textit{Entrées} : $ J $ et $ g $ de classe $ \mathcal{C}^2 $, $ \varepsilon = 0.01 $, $ (x_0,y_0,z_0) = (100, 100 ,0)$ et $(\lambda_{0_1},\lambda_{0_2}) = (1 , 1)$, les rayons : $r= 100$ et $r1 = r2 = 10$.
+ \newline
+ Le Lagrangien $ L $ de $ \mathcal{P} $ : $$ L((x,y,z),(\lambda_1,\lambda_2)) = x^2 + y^2 + z^2 -r^2 + \lambda_1(x^2 + y^2 - r_1^2) + \lambda_2(x^2 + z^2 -r_2^2). $$
+ \newline
+ Le Lagrangien $ L $ de $ \mathcal{P} $ avec les valeurs :
+ $ L((100,100,0),(1,1)) = 100^2 + 100^2 + 0^2 -100^2 + 1 * (100^2 +100^2 - 10^2) + \lambda_2(100^2 + 100^2 -10^2). $
+ $ L((100,100,0),(1,1)) = 1000 + 1000 - 1000 + (1000 + 1000 - 100) + (1000 + 1000 -100). $
+ $ L((100,100,0),(1,1)) = 4800. $
- \STATE {//Première itération :}
+ \newpage
+ \begin{algorithmfloat}[#Algo 1]
+ \caption {Trace d'éxécution du PQS du problème $ \mathcal{P} $}
+ \begin{algorithmic}
+ \REQUIRE $g(x_0,y_0,z_0)\leq 0$, $(x_0,y_0,z_0) = (10, 10 ,10)$
+ \ENSURE $\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2$ and \newline $g(x,y,z) = (g_1(x,y,z), g_2(x,y,z)) = (x^2 + y^2 - r_1^2, x^2 + z^2 -r_2^2) \leq 0 $
+ \STATE \textbf{Data :}
+ \STATE $k \leftarrow 0, (x_k, y_k, z_k) \leftarrow (100, 100, 0), r \leftarrow 100$
+ \STATE $r_1 = r2 \leftarrow 10, \varepsilon \leftarrow 0.01$
+ \STATE $\lambda_1 = \lambda_2 = 1$
+ \STATE $ H[J](x,y,z)^{-1}\leftarrow \begin{pmatrix}
+ 0.5 & 0 & 0 \\
+ 0 & 0.5 & 0 \\
+ 0 & 0 & 0.5 \\ \end{pmatrix} $
+ \newline
- \STATE{//Calcul du gradient de $ J $ :}
- \STATE $\nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (160,40,120)$
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (100,100,0) $
+ \newline
+ \STATE {//calcule des deux sous partie de du gradient de $ g $: }
+ \STATE $ \nabla g_1(x_a,y_a,z_a) = ((2x_a,2y_a,0)$ \hfill $ //résultat : (20, 20, 0)$
+ \STATE $ \nabla g_2(x_a,y_a,z_a) = (2x_a,0,2z_a))$ \hfill $ //résultat : (20, 0, 20)$
+ \STATE $ \nabla g(x_k,y_k,z_k) = (\nabla g_1(x_k,y_k,z_k), \nabla g_2(x_k,y_k,z_k))$
+ \newline
+ \WHILE{$ (\norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $ or k $ \leq 10)$}
- \STATE {//Calcul des deux composantes du gradient de $ g $ :}
- \STATE $\nabla g_1(x_k,y_k,z_k) = ((2x_k,2y_k,0)$ \hfill $ //résultat : (60, 20, 0)$
- \STATE $\nabla g_2(x_k,y_k,z_k) = (2x_k,0,2z_k))$ \hfill $ //résultat : (60, 0, 80)$
- \STATE $\nabla g(x_k,y_k,z_k) = (\nabla g_1(x_k,y_k,z_k), \nabla g_2(x_k,y_k,z_k))$
+ \STATE { //première itération :}
- \STATE {//Calcul du gradient de $ L $ :}
- \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k) $ \hfill $ //résultat : (280, 60, 200)$
+ \STATE {//Calcule du gradient de $ L $ : }
+ \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (220, 220, 40)$
+ \STATE $ \nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = (x_L , y_L, z_L) $
+ \newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(50,50,0))$
+ \newline
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (50,50,0)$
+ \newline
+ \STATE {//Incrémentation de k}
+ \STATE $ k \leftarrow k+1$\hfill $ //k = 1$
+ \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
- \STATE $ d_k = -H[J](x,y,z)^{-1}*\nabla J(x,y,z)$ \hfill $ //résultat : (-(80,20,60))$
+ \STATE {//Deuxième itération :}
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (100,100,0) $
+ \newline
+ \STATE {//Calcule du gradient de $ L $ : }
+ \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (120, 120, 0)$
+ \STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(25,25,0))$
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (25,25,0)$
+ \newline
+ \STATE {//Incrémentation de k}
+ \STATE $ k \leftarrow k+1$\hfill $ //k = 2$
+ \newline
- \STATE {//Calcul des nouvelles valeurs des coordonnées :}
- \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (0,0,0)$
+ \STATE {//Troisième itération :}
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (50,50,0) $
+ \newline
+ \STATE {//Calcule du gradient de $ L $ : }
+ \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (70, 70, 0)$
+ \STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(12.5,12.5,0))$
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \newline
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (12.5,12.5,0)$
+ \STATE {//Incrémentation de k}
+ \STATE $ k \leftarrow k+1$\hfill $ //k = 3$
+ \newline
- \STATE {//Deuxième itération :}
+ \STATE {//Quatrième itération :}
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (25,25,0) $
+ \newline
+ \STATE {//Calcule du gradient de $ L $ : }
+ \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (45, 45, 0)$
+ \STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(6.25,6.25,0))$
+ \newline
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (6.25,6.25,0)$
+ \STATE {//Incrémentation de k}
+ \newline
+ \STATE $ k \leftarrow k+1$\hfill $ //k = 4$
+ \STATE $ $
- \STATE {//Incrémentation de k}
- \STATE $ k \leftarrow k+1$ \hfill $ //résultat : 1$
+ \STATE {//Cinquième itération :}
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (12.5,12.5,0) $
+ \newline
+ \STATE {//Calcule du gradient de $ L $ : }
+ \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (32.5, 32.5, 0)$
+ \STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(3.125,3.125,0))$
+ \newline
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (3.125,3.125,0)$
+ \newline
+ \STATE {//Incrémentation de k}
+ \STATE $ k \leftarrow k+1$\hfill $ //k = 5$
+ \newline
- \STATE{//Calcul du gradient de $ J $ :}
- \STATE $\nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (0,0,0)$
+ \STATE {//Sixième itération :}
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (6.25,6.25,0) $
+ \newline
+ \STATE {//Calcule du gradient de $ L $ : }
+ \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (26.25, 26.25, 0)$
+ \STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(1.5625,1.5625,0))$
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \newline
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (1.5625,1.5625,0)$
+ \STATE {//Incrémentation de k}
+ \newline
+ \STATE $ k \leftarrow k+1$\hfill $ //k = 6$
+ \newline
- \STATE {//Calcul des deux composantes du gradient de $ g $ :}
- \STATE $\nabla g_1(x_k,y_k,z_k) = ((2x_k,2y_k,0)$ \hfill $ //résultat : (60, 20, 0)$
- \STATE $\nabla g_2(x_k,y_k,z_k) = (2x_k,0,2z_k))$ \hfill $ //résultat : (60, 0, 80)$
- \STATE $\nabla g(x_k,y_k,z_k) = (\nabla g_1(x_k,y_k,z_k), \nabla g_2(x_k,y_k,z_k))$
+ \STATE {//Septième itération :}
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (3.125, 3.125, 0) $
+ \newline
+ \STATE {//Calcule du gradient de $ L $ : }
+ \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (23.125, 23.125, 0)$
+ \STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.78125,0.78125,0))$
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \newline
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0.78125,0.78125,0)$
+ \STATE {//Incrémentation de k}
+ \newline
+ \STATE $ k \leftarrow k+1$\hfill $ //k = 7$
+ \newline
- \STATE {//Calcul du gradient de $ L $ :}
- \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_k,y_k,z_k) + \lambda_2 \nabla g_2(x_k,y_k,z_k)) $ \hfill $ //résultat : (160, 20, 30)$
+ \STATE {//Huitième itération :}
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (1.5625, 1.5625, 0) $
+ \newline
+ \STATE {//Calcule du gradient de $ L $ : }
+ \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (21.5625, 21.5625, 0)$
+ \STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.390625,0.390625,0))$
+ \newline
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0.390625,0.390625,0)$
+ \newline
+ \STATE {//Incrémentation de k}
+ \STATE $ k \leftarrow k+1$\hfill $ //k = 8$
+ \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (méthode de Newton) :}
- \STATE $ d_k = -H[J](x_k,y_k,z_k)^{-1} * \nabla J(x,y,z)$ \hfill $ //résultat : (-(0,0,0))$
+ \STATE {//neuvième itération :}
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (0.78125, 0.78125, 0) $
+ \newline
+ \STATE {//Calcule du gradient de $ L $ : }
+ \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (20.78125, 20.78125, 0)$
+ \STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.1953125,0.1953125,0))$
+ \newline
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0.1953125,0.1953125,0)$
+ \newline
+ \STATE {//Incrémentation de k}
+ \STATE $ k \leftarrow k+1 \hfill //k = 9$
+ \newline
- \STATE {//Calcul des nouvelles valeurs des coordonnées :}
- \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + d_k $ \hfill $ //résultat : (0,0,0)$
+ \STATE {//Dixième itération :}
+ \STATE{//Calcule du gradient de $ J $ :}
+ \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (0.390625, 0.390625, 0) $
+ \newline
+ \STATE {//Calcule du gradient de $ L $ : }
+ \STATE $\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) = \nabla J(x_k,y_k,z_k) + \lambda_1 \nabla g_1(x_a,y_a,z_a) + \lambda_2 \nabla g_2(x_a,y_a,z_a)) $ \hfill $// résultat : (20.390625, 20.390625, 0)$
+ \STATE $ \varepsilon _1 = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \newline
+ \STATE {//Calcule de la direction de la pente dk (méthode de Newton) : }
+ \STATE $ d_k = -H[J](x,y,z)^{-1}* J(x,y,z)$ \hfill $ //résultat : (-(0.097665625,0.097665625,0))$
+ \newline
+ \STATE {//Calcul nouvelles valeurs des coordonnées}
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k)+ d_k $ \hfill $ //résultat : (0.097665625,0.097665625,0)$
+ \newline
+ \STATE {//Incrémentation de k}
+ \STATE $ k \leftarrow k+1$\hfill $ //k = 10$
+ \newline
+ \STATE {// Fin de la boucle "while" car nous avons atteint k =10, condition mettant fin à la //boucle}
+ \newline
- \ENDWHILE
+ \ENDWHILE
- \end{algorithmic}
- \end{algorithm}
+ \end{algorithmic}
+ \end{algorithmfloat}
\hrulefill
repositories / Projet_Recherche_Operationnelle.git / commitdiff
