\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}
\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) = (80, 20 ,60)$ et $(\lambda_{0_1},\lambda_{0_2}) = (1 , 1)$, les rayons : $r= 40$ et $r1 = r2 = 10$.
+\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((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). $
- $ L((80,20,60),(1,1)) = 6400 + 400 + 3600 - 3600 + (6400 + 400 - 900) + (6400 + 3600 -900). $
- $ L((80,20,60),(1,1)) = 21800. $
+ $ 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. $
- \begin{algorithm}
- \caption {PQS du problème $ \mathcal{P} $}
+\newpage
+\begin{algorithmfloat}[#Algo 1]
+ \caption {Trace d'éxécution du PQS du problème $ \mathcal{P} $}
\begin{algorithmic}
- \REQUIRE $g(x,y,z)\leq 0$, $(x_0,y_0,z_0) = (80, 20 ,60)$
+ \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$
- \STATE $x_k \leftarrow 80$
- \STATE $y_k \leftarrow 20$
- \STATE $z_k \leftarrow 60$
- \STATE $x_a \leftarrow 30$
- \STATE $y_a \leftarrow 10$
- \STATE $z_a \leftarrow 40$
- \STATE $r \leftarrow 40$
- \STATE $r_1 \leftarrow 10$
- \STATE $r_2 \leftarrow 10$
- \STATE $\varepsilon \leftarrow 0.01$
+ \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 \\
\newline
\STATE{//Calcule du gradient de $ J $ :}
- \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ // résultat : (160,40,120) $
+ \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(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 $ \nabla g_1(x_a,y_a,z_a) = ((2x_a,2y_a,0)$ \hfill $ //résultat : (60, 20, 0)$
- \STATE $ \nabla g_2(x_a,y_a,z_a) = (2x_a,0,2z_a))$ \hfill $ //résultat : (60, 0, 80)$
+ \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 $ < 10)$}
+ \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 : (280, 60, 200)$
+\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}*\nabla J(x,y,z)$ \hfill $ //résultat : (-(80,20,60))$
+ \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 : (0,0,0)$
+ \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$
-
+ \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 : (0,0,0) $
-
+ \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 : (160, 20, 30)$
- \STATE $ (\varepsilon ,\varepsilon ,\varepsilon ) = \nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2)) $
-
+\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}*\nabla J(x,y,z)$ \hfill $ //résultat : (-(0,0,0))$
+ \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 : (0,0,0)$
+ \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 = 1$
+\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{algorithm}
+\end{algorithmfloat}
\hrulefill
repositories / Projet_Recherche_Operationnelle.git / blobdiff