X-Git-Url: https://git.piment-noir.org/?p=Projet_Recherche_Operationnelle.git;a=blobdiff_plain;f=rapport%2FProjetOptimRO.tex;h=ccce4d2d1ae6ad6280595a3c715deff9bdb60f71;hp=bd12bfa7b51a638c6e57cacf20b138a453d7e996;hb=70b2e2fca29d0317292896b234fb92666d6ff7ac;hpb=46973afbb2be010f0e7732f29b7d7c79c002568e diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index bd12bfa..ccce4d2 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -21,6 +21,8 @@ \usepackage{tocbibind} \usepackage{lmodern} \usepackage{enumitem} +\usepackage{algorithm2e} +\usepackage{algorithmic} %%%%%Marges & en-t\^etes @@ -283,7 +285,7 @@ Définissons quelques notions supplémentaires de base nécessaires à la suite $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle = \nabla f(x^\ast)^\top h $ \end{Rmq} \begin{Def} - Soit $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ un fonction de classe $ \mathcal{C}^2 $. + Soit $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ une fonction de classe $ \mathcal{C}^2 $. On définit la matrice hessienne de $ f $ en $ x^\ast $ par : $$ H[f](x^\ast) = \begin{pmatrix} @@ -514,7 +516,7 @@ En supposant $ J $ de classe $ \mathcal{C}^2 $ et la matrice hessienne $ H[J](x_ $$ x_{k+1} = x_k - H[J](x_k)^{-1} \nabla J(x_k), $$ où $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ est appelée direction de Newton. La direction $ d_k $ est également l’unique solution du problème : $$ \underset{d \in \mathbb{R}^n}{\mathrm{argmin}} \ J(x_k) + \langle \nabla J(x_k),d \rangle + \frac{1}{2}\langle H[J](x_k)d,d \rangle $$ -Autrement dit, $ d_k $ est le point de minimum global de l’approximation de second ordre de $ J $ au voisinage du point courant $ x_k $. +Autrement dit, $ d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $. À condition que la matrice $ H[J](x_k) $ soit définie positive à chaque itération, la méthode de Newton est bien une méthode de descente à pas fixe égal à $ 1 $. \newline Les propriétés remarquables de cet algorithme sont : @@ -553,9 +555,32 @@ Nous ne répondrons pas à ces questions qui sont hors du cadre de ce projet. Ce Nous supposons les fonctions $ J,g,h $ à valeurs réelles et de classe $ \mathcal{C}^1 $. Trouver une solution d’un problème d’optimisation sous contraintes fonctionnelles consiste à déterminer un point optimal $ x^\ast $ et des multiplicateurs associés $ (\lambda^\ast,\mu^\ast) $. Deux grandes familles de méthodes peuvent être définies pour la résolution des problèmes d’optimisation sous contraintes : les méthodes primales et les méthodes duales. Les approches primales se concentrent sur la détermination du point $ x^\ast $, les multiplicateurs $ (\lambda,\mu) $ ne servant souvent qu’à vérifier l’optimalité de $ x^\ast $. Les méthodes duales quant à elles mettent l’accent sur la recherche des multiplicateurs en travaillant sur un problème d’optimisation déduit du problème initial par \textit{dualité}. +\subsection{Problème quadratique sous contraintes linéaires} + +Nous introduisons les différentes approches développées pour la résolution des problèmes de programmation quadratique avec contraintes d'égalités et d’inégalités linéaires. +\newline +Ce type de problème quadratique se pose sous la forme : +$$ + \mathcal{PQ} \left \{ + \begin{array}{l} + \displaystyle\min_{x \in \mathbb{R}^n} c^\top x + \frac{1}{2} x^\top \mathcal{Q} x \\ + A^\top x + b \leq 0 \\ + A^{\prime^\top} x + b^\prime = 0 + \end{array} + \right . +$$ +où $$ \mathcal{Q} \in \mathcal{M}_n(\mathbb{R}) \ symétrique, c \in \mathbb{R}^n, A \in \mathcal{M}_{n,p}(\mathbb{R}), b \in \mathbb{R}^p, A^\prime \in \mathcal{M}_{n,q}(\mathbb{R}), b^\prime \in \mathbb{R}^q $$ +Or +$$ A^{\prime^\top} x + b^\prime = 0 \iff A^{\prime^\top} x + b^\prime \leq 0 \land -A^{\prime^\top} x - b^\prime \leq 0 $$ +Donc le problème se ramène à : + +\subsubsection{Algorithme 1} + +\subsubsection{Algorithme 2} + \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} @@ -711,7 +736,7 @@ ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INEGALITÉ. \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 = 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 . @@ -759,25 +784,267 @@ $$ \right . $$ où $$ (r,r_1,r_2) \in \mathbb{R}_+^3. $$ -Les hypothèses : $ J $ et $ g $ sont de classe $ \mathcal{C}^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). $$ \newline -Le Lagrangien de $ \mathcal{P} $ : $ L(x,y,z,\lambda) = $ +Le gradient de $ J $ : $$ \nabla J(x,y,z) = (\frac{\partial J}{\partial x}(x,y,z),\frac{\partial J}{\partial y}(x,y,z),\frac{\partial J}{\partial z}(x,y,z)) = (2x,2y,2z). $$ \newline -Le gradient de $ J $ : $ \nabla J(x,y,z) = (\frac{\partial J}{\partial x}(x,y,z),\frac{\partial J}{\partial y}(x,y,z),\frac{\partial J}{\partial z}(x,y,z)) = $ +Le gradient de $ g $ : $$ \nabla g(x,y,z) = (\nabla g_1(x,y,z),\nabla g_2(x,y,z)) $$ +$$ = ((\frac{\partial g_1}{\partial x}(x,y,z),\frac{\partial g_1}{\partial y}(x,y,z),\frac{\partial g_1}{\partial z}(x,y,z)),(\frac{\partial g_2}{\partial x}(x,y,z),\frac{\partial g_2}{\partial y}(x,y,z),\frac{\partial g_2}{\partial z}(x,y,z)) $$ +$$ = ((2x,2y,0),(2x,0,2z)). $$ \newline -Le gradient de $ g $ : $ \nabla g(x,y,z) = (\nabla g_1(x,y,z),\nabla g_2(x,z,z)) = $ +Le gradient du Lagrangien $ L $ : +$$ \nabla L((x,y,z),(\lambda_1,\lambda_2)) = \nabla J(x,y,z) + \lambda_1 \nabla g_1(x,y,z) + \lambda_2 \nabla g_2(x,y,z)) $$ \newline -La matrice hessienne de $ J $ : $ H[J](x,y,z) = +La matrice hessienne de $ J $ : $$ H[J](x,y,z) = \begin{pmatrix} \frac{\partial^2 J}{\partial^2 x}(x,y,z) & \frac{\partial^2 J}{\partial x\partial y}(x,y,z) & \frac{\partial^2 J}{\partial x\partial z}(x,y,z) \\ \frac{\partial^2 J}{\partial y\partial x}(x,y,z) & \frac{\partial^2 J}{\partial^2 y}(x,y,z) & \frac{\partial^2 J}{\partial y\partial z}(x,y,z) \\ \frac{\partial^2 J}{\partial z\partial x}(x,y,z) & \frac{\partial^2 J}{\partial z\partial y}(x,y,z) & \frac{\partial^2 J}{\partial^2 z}(x,y,z) \\ \end{pmatrix} = \begin{pmatrix} - & & \\ - & & \\ - & & \\ - \end{pmatrix} $ + 2 & 0 & 0 \\ + 0 & 2 & 0 \\ + 0 & 0 & 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} $. + +\hrulefill + +\subsection{Trace d'éxécution de PQS} + +Utilisons le problème $ \mathcal{P} $ précédent : + +$$ + \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. $ + +\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{//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 { //première itération :} + +\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 {//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 {//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 {//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 {//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 {//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 {//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 {//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 {//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 {//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 + +\end{algorithmic} +\end{algorithmfloat} + + +\hrulefill \bibliographystyle{plain} \bibliography{stdlib_sbphilo}