\usepackage{enumitem}
\usepackage{algorithm2e}
\usepackage{algorithmic}
+\usepackage{float}
%%%%%Marges & en-t\^etes
\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 à :
+% 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 $$
+On peut ramener le problème à :
+$$
+ \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 + z = 0 \\
+ A^{\prime^\top} x + b^\prime = 0
+ \end{array}
+ \right .
+$$
+où $$ z \in \mathbb{R}^p $$
+On peut donc ramener l'étude de ce type de problème à :
+$$
+ \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 = 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 $$
+Conditions \textit{KKT} appliquées à $ \mathcal{PQ} $ :
+$$
+ \begin{array}{r c l}
+ \mathcal{Q} x + A \lambda^\ast & = & - c \\
+ A^\top x & = & -b \\
+ \end{array}
+$$
+On obtient donc :
+$$ \lambda^\ast = (A^\top \mathcal{Q} A)^{-1} A^\top \mathcal{Q} c $$
+En posant $ \mathcal{Q} = Id_{\mathbb{R}^n} $, on a une bonne évaluation de $ \lambda^\ast $ :
+$$ \lambda^\ast = (A^\top A)^{-1} A^\top c $$
-\subsubsection{Algorithme 1}
+\subsubsection{Méthode des points intérieurs}
-\subsubsection{Algorithme 2}
+Soit $ F_\mu $ définit par :
+$$ F_\mu(x, \lambda, s) =
+ \begin{pmatrix}
+ \mathcal{Q}x - A^\top \lambda -s -c \\
+ A x + b \\
+ XS - \mu
+ \end{pmatrix}
+$$
+où
+$$ X = diag(x) \in \mathcal{M}_n(\mathbb{R}), S = diag(s) \in \mathcal{M}_n(\mathbb{R}), s > 0 \ et \ \mu \in \mathbb{R}^n $$
+\hrulefill
+\newline
+ALGORITHME DES POINTS INTÉRIEURS.
+\newline
+\textit{Entrées}: $ F_\mu : \mathbb{R}^n \times \mathbb{R}^p \times \mathbb{R}^n \longrightarrow \mathcal{M}_{n,2n+p}(\mathbb{R}) $, $ (x_0,\lambda_0,s_0) \in \mathbb{R}^n \times \mathbb{R}^p \times \mathbb{R}^n $ où $ (x_0,s_0) > 0 $ point initial arbitraire, $ \varepsilon > 0 $ précision demandée.
+\newline
+\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $, avec son coefficient $ \lambda_k $, du problème $ \mathcal{PQ} $.
+\begin{enumerate}
+ \item $ k := 0 $.
+ \item Tant que $ \frac{x_k^\top s_k}{n} > \varepsilon $,
+ \begin{enumerate}
+ \item Choisir $ \sigma_k \in [\sigma_{min},\sigma_{max}]$
+ \item Résoudre le sytème linéaire d'équations où $ J_{F_\mu}(x_k,\lambda_k,s_k) $ désigne la matrice jacobienne de $ F_\mu $:
+ $$ J_{F_\mu}(x_k,\lambda_k,s_k) d = -
+ \begin{pmatrix}
+ \mathcal{Q}x - A^\top \lambda -s -c \\
+ A x + b \\
+ XS - \sigma_k \mu
+ \end{pmatrix} $$
+ pour déterminer $ d_k = (d_{x_k},d_{\lambda_k},d_{s_k}) $.
+ \item Choisir $ \alpha_{max} $ la plus grande valeur $ \alpha $ tel que $ (x_k,s_k) + \alpha(d_{x_k},d_{s_k}) > 0 $.
+ \item Choisir $ \alpha_k = \min \{1, \eta_k \sigma_{max} $ tel que $ \exists \eta_k \in [0,1]\} $.
+ \item $ \mu_k = \frac{x_k^\top s_k}{n} $; $ (x_{k+1},\lambda_{k+1},s_{k+1}) := (x_k,\lambda_k,s_k) + \alpha_k d_k $; $ k := k + 1 $.
+ \end{enumerate}
+ \item Retourner $ (x_k,\lambda_k,s_k) $.
+\end{enumerate}
+
+\hrulefill
+\newline
+On note que c'est un algorithme de descente avec recherche d'un pas optimal.
+La détermination de $ \sigma_{min} $ et $ \sigma_{max} $ se fait dans l'intervalle ouvert $ ]0, 1[ $. Il existe d'autres méthodes de résolution du problème $ \mathcal{PQ} $ mais celle-ci à l'avantage de passer à l'échelle et a des vitesses de convergence efficientes. La résolution du système linéaire d'équations peut être faite soit directement, soit en utilisant une méthode itérative de résolution de problèmes d'algèbre linéaire.
\subsection{Algorithmes Newtoniens}
$$ \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) = 0 \iff \nabla L(x,\lambda) = 0 $$
donc $ \mathcal{P} $ devient :
$$ \begin{pmatrix}
- \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) \\
- h(x)
- \end {pmatrix} = 0 $$
+ \nabla J(x) + \sum\limits_{i=1}^{q} \lambda_i \nabla h_i(x) \\
+ h(x)
+ \end{pmatrix} = 0 $$
Pour résoudre ce système d’équations, utilisons la méthode de Newton dont une itération s’écrit ici :
$$ H[L](x_k,\lambda_k)\begin{pmatrix}
x_{k+1} - x_k \\
$$ g(x) \approx g(x_k) + \nabla g(x_k)^\top(x - x_k) $$
$$ h(x) \approx h(x_k) + \nabla h(x_k)^\top(x - x_k) $$
En posant $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $, on obtient le sous problème quadratique $ \mathcal{PQ}_k $ :
-
+$$
+ \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(x_k) + \nabla g(x_k)^\top d \leq 0 \\
+ h(x_k) + \nabla h(x_k)^\top d = 0
+ \end{array}
+ \right .
+$$
+Comme pour la cas précédent, on résoud alors le sous problème quadratique $ \mathcal{PQ}_k $ qui est plus simple avec une méthode vue plus haut en posant $ \mathcal{Q} = H_k = H[L](x_k,\lambda_k,\mu_k) $.
+\newpage
\hrulefill
\newline
ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ.
\newline
Afin que le sous-programme quadratique $ \mathcal{PQ}_k $ admette une unique solution, la plupart des implémentations actuelles de PQS utilisent une approximation du hessien $ H_k $ du Lagrangien qui soit définie positive, en particulier celle fournie par les techniques quasi-newtonienne (BFGS) par exemple.
\newline
-Etant une méthode newtonienne, l’algorithme PQS converge localement quadratiquement pourvu que les points initiaux $ (x_0,\lambda_0 ) $ (resp. $ (x_0,\lambda_0,\mu_0) $) soient dans un voisinage d’un point stationnaire $ \overline{x} $ et de ses multiplicateurs associés $ \overline{\lambda} $ (resp. $ (\overline{\lambda},\overline{\mu}) $). Bien entendu, il est possible de globaliser l’algorithme en ajoutant une étape de recherche linéaire.
+Étant une méthode newtonienne, l’algorithme PQS converge localement quadratiquement pourvu que les points initiaux $ (x_0,\lambda_0 ) $ (resp. $ (x_0,\lambda_0,\mu_0) $) soient dans un voisinage d’un point stationnaire $ \overline{x} $ et de ses multiplicateurs associés $ \overline{\lambda} $ (resp. $ (\overline{\lambda},\overline{\mu}) $). Bien entendu, il est possible de globaliser l’algorithme en ajoutant une étape de recherche linéaire.
\subsection{Stratégie d'approximation de la hessienne}
\newline
Une stratégie commune est de calculer $ (x_{k+1},\lambda_{k+1},\mu_{k+1}) $ pour une matrice $ H_k $ donnée et faire une mise à jour de $ H_k $ de rang 1 ou 2 :
$$ H_{k+1} = H_k + U_k $$
-% \subsubsection{Mises à jour DFP et BFGS}
-Les méthodes de mise à jour DFP et BFGS suivent par exemple cette stratégie.
+Les méthodes de mises à jour PSB et BFGS suivent par exemple cette stratégie.
+
+\subsubsection{Mises à jour PSB}
+
+$$ H_{k+1} = H_k + \frac{1}{d^\top d} ((y - H_k d)d^\top + d(y - H_k d)^\top) - \frac{(y - H_k d)^\top d}{(d^\top d)^2}d^\top d $$
+où
+$$ d = x_{k+1} - x_k $$
+$$ y = \nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1}) $$
+
+\subsubsection{Mises à jour BFGS}
+
+$$ H_{k+1} = H_k + \frac{y y^\top}{y^\top d} - \frac{H_k d d^\top H_k}{d^\top H_k d}$$
+où
+$$ d = x_{k+1} - x_k $$
+$$ y = \nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1}) $$
\subsection{Exemple d'utilisation de PQS}
\newline
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)) $$
+$$ = (2x(1 + \lambda_1 + \lambda_2),2y(1 + \lambda_1),2z(1 + \lambda_2)) $$
\newline
La matrice hessienne de $ J $ : $$ H[J](x,y,z) =
\begin{pmatrix}
\newpage
-\subsection{Trace d'éxécution de l'algorithme PQS}
+\subsection{Trace d'éxécution de l'algorithme pour la méthode de Newton}
\begin{center}
\includegraphics[scale=0.2]{sphere2.jpg} \\
\newline
Calcul du Lagrangien $ L $ de $ \mathcal{P} $ en $(x_0,y_0,z_0)$ :
\newline
-$ L((100,100,0),(1,1)) = 100^2 + 100^2 + 0^2 -100^2 + 1 * (100^2 +100^2 - 10^2) + 1 * (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)) = 100^2 + 100^2 + 0^2 - 100^2 + 1 * (100^2 +100^2 - 10^2) + 1 * (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
+\textbf{Trace d'éxécution de l'algorithme :}
+\newline
+\newfloat{algorithm}{t}
+
+\begin{algorithmic}
+ \REQUIRE $(x_0,y_0,z_0) = (100, 100 ,0), g(x_0,y_0,z_0) \leq 0$
+ \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$
+ \STATE \textbf{Data :}
+ \STATE $k \leftarrow 0, (x_k, y_k, z_k) \leftarrow (100, 100, 0), r \leftarrow 100$
+ \STATE $r_1 = r_2 \leftarrow 10, \varepsilon \leftarrow 0.01$
+ \STATE $\lambda_1 = \lambda_2 \leftarrow 1$
+ \STATE $s_k \leftarrow \frac{1}{2}$
+ \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
+
+ \WHILE{$ (\norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $ or k $ \leq 10)$}
+
+ \STATE {//Première itération :}
+ \STATE {//Calcul du gradient de $ J $ :}
+ \STATE $ \nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (200,200,0) $
+ \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 : (200, 200, 0)$
+ % \STATE $ \nabla g_2(x_k,y_k,z_k) = (2x_k,0,2z_k)$ \hfill $ //résultat : (200, 0, 0)$
+ % \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
+ \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 : (6*100, 4*100, 0)$
+ \STATE $ \varepsilon_k = \norme{\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)) = (x_L , y_L, z_L) $
+ \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_k,y_k,z_k) $ \hfill $ //résultat : (-(100,100,0))$
+ \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) + s_k d_k $ \hfill $ //résultat : (50,50,0)$
+ \newline
+ \STATE {//Incrémentation de $ k $}
+ \STATE $ k \leftarrow k + 1 $ \hfill $ //résultat : k = 1$
+ \newline
+
+ \STATE {//Deuxième itération :}
+ \STATE {//Calcul du gradient de $ J $ :}
+ \STATE $ \nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (100,100,0) $
+ \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 : (6*50, 4*50, 0)$
+ \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \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_k,y_k,z_k) $ \hfill $ //résultat : (-(50,50,0))$
+ \STATE {//Calcul des nouvelles valeurs des coordonnées}
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + s_k d_k $ \hfill $ //résultat : (25,25,0)$
+ \newline
+ \STATE {//Incrémentation de $ k $ }
+ \STATE $ k \leftarrow k + 1 $ \hfill $ //résultat : k = 2$
+ \newline
+
+ \STATE {//Troisième itération :}
+ \STATE {//Calcul du gradient de $ J $:}
+ \STATE $ \nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (50,50,0) $
+ \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 : (6*25, 4*25, 0)$
+ \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \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_k,y_k,z_k) $ \hfill $ //résultat : (-(25,25,0))$
+ \STATE {//Calcul des nouvelles valeurs des coordonnées}
+ \newline
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + s_k d_k $ \hfill $ //résultat : (12.5,12.5,0)$
+ \STATE {//Incrémentation de $ k $}
+ \STATE $ k \leftarrow k + 1 $ \hfill $ //résultat : k = 3$
+ \newline
+
+ \STATE {//Quatrième itération :}
+ \STATE {//Calcul du gradient de $ J $ :}
+ \STATE $ \nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (25,25,0) $
+ \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 : (6*12.5, 4*12.5, 0)$
+ \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \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_k,y_k,z_k) $ \hfill $ //résultat : (-(12.5,12.5,0))$
+ \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) + s_k d_k $ \hfill $ //résultat : (6.25,6.25,0)$
+ \STATE {//Incrémentation de $ k $}
+ \newline
+ \STATE $ k \leftarrow k + 1 $ \hfill $ //résultat : k = 4$
+ \newline
+
+ \STATE {//Cinquième itération :}
+ \STATE {//Calcul du gradient de $ J $ :}
+ \STATE $ \nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (12.5,12.5,0) $
+ \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 : (6*6.25, 4*6.25, 0)$
+ \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \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_k,y_k,z_k) $ \hfill $ //résultat : (-(6.25,6.25,0))$
+ \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) + s_k d_k $ \hfill $ //résultat : (3.125,3.125,0)$
+ \newline
+ \STATE {//Incrémentation de $ k $}
+ \STATE $ k \leftarrow k + 1 $ \hfill $ //résultat : k = 5$
+ \newline
+
+ \STATE {//Sixième itération :}
+ \STATE {//Calcul du gradient de $ J $ :}
+ \STATE $ \nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (6.25,6.25,0) $
+ \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 : (6*3.125, 4*3.125, 0)$
+ \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \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_k,y_k,z_k) $ \hfill $ //résultat : (-(3.125,3.125,0))$
+ \STATE {//Calcul des nouvelles valeurs des coordonnées}
+ \newline
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + s_k d_k $ \hfill $ //résultat : (1.5625,1.5625,0)$
+ \STATE {//Incrémentation de $ k $}
+ \newline
+ \STATE $ k \leftarrow k + 1 $ \hfill $ //résultat : k = 6$
+ \newline
+
+ \STATE {//Septième itération :}
+ \STATE {//Calcul du gradient de $ J $ :}
+ \STATE $ \nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (3.125, 3.125, 0) $
+ \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 : (6*1.5625, 4*1.5625, 0)$
+ \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \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_k,y_k,z_k) $ \hfill $ //résultat : (-(1.5625,1.5625,0))$
+ \STATE {//Calcul des nouvelles valeurs des coordonnées}
+ \newline
+ \STATE $ (x_{k+1},y_{k+1},z_{k+1}) = (x_k,y_k,z_k) + s_k d_k $ \hfill $ //résultat : (0.78125,0.78125,0)$
+ \STATE {//Incrémentation de $ k $}
+ \newline
+ \STATE $ k \leftarrow k + 1 $ \hfill $ //résultat : k = 7$
+ \newline
+
+ \STATE {//Huitième itération :}
+ \STATE{//Calcul du gradient de $ J $ :}
+ \STATE $ \nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (1.5625, 1.5625, 0) $
+ \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 : (6*0.78125, 4*0.78125, 0)$
+ \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \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_k,y_k,z_k) $ \hfill $ //résultat : (-(0.78125,0.78125,0))$
+ \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) + s_k d_k $ \hfill $ //résultat : (0.390625,0.390625,0)$
+ \newline
+ \STATE {//Incrémentation de $ k $}
+ \STATE $ k \leftarrow k + 1 $ \hfill $ //résulat : k = 8$
+ \newline
+
+ \STATE {//Neuvième itération :}
+ \STATE {//Calcul du gradient de $ J $ :}
+ \STATE $ \nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (0.78125, 0.78125, 0) $
+ \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 : (6*0.390625, 4*0.390625, 0)$
+ \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \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_k,y_k,z_k) $ \hfill $ //résultat : (-(0.390625,0.390625,0))$
+ \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) + s_k d_k $ \hfill $ //résultat : (0.1953125,0.1953125,0)$
+ \newline
+ \STATE {//Incrémentation de $ k $}
+ \STATE $ k \leftarrow k + 1 \hfill //résultat : k = 9$
+ \newline
+
+ \STATE {//Dixième itération :}
+ \STATE {//Calcul du gradient de $ J $ :}
+ \STATE $ \nabla J(x_k,y_k,z_k) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (0.390625, 0.390625, 0) $
+ \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 : (6*0.1953125, 4*0.1953125, 0)$
+ \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
+ \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_k,y_k,z_k) $ \hfill $ //résultat : (-(0.1953125,0.1953125,0))$
+ \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) + s_k d_k $ \hfill $ //résultat : (0.097665625,0.097665625,0)$
+ \newline
+ \STATE {//Incrémentation de $ k $}
+ \STATE $ k \leftarrow k + 1 $ \hfill $ //résultat : k = 10$
+ \newline
+ \STATE {//Fin de la boucle "while" car nous avons atteint $ k = 10 $, condition mettant fin à la //boucle}
+ \newline
+
+ \ENDWHILE
-% \begin{algorithmfloat}[#Algo 1]
-\begin{algorithm}
- \caption {Trace d'éxécution de l'algorithme PQS}
- \begin{algorithmic}
- \REQUIRE $(x_0,y_0,z_0) = (100, 100 ,0), g(x_0,y_0,z_0) \leq 0$
- \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 $
- \STATE \textbf{Data :}
- \STATE $k \leftarrow 0, (x_k, y_k, z_k) \leftarrow (100, 100, 0), r \leftarrow 100$
- \STATE $r_1 = r_2 \leftarrow 10, \varepsilon \leftarrow 0.01$
- \STATE $\lambda_1 = \lambda_2 \leftarrow 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 {//Pré-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 : (20, 20, 0)$
- \STATE $ \nabla g_2(x_k,y_k,z_k) = (2x_k,0,2z_k))$ \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{//Calcul du gradient de $ J $ :}
- \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (100,100,0) $
- \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 : (220, 220, 40)$
- \STATE $ \varepsilon_k = \norme{\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)) = (x_L , y_L, z_L) $
- \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (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 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 : (50,50,0)$
- \newline
- \STATE {//Incrémentation de $ k $}
- \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 1$
- \newline
-
- \STATE {//Deuxième itération :}
- \STATE{//Calcul du gradient de $ J $ :}
- \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (100,100,0) $
- \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 : (120, 120, 0)$
- \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
- \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (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 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 : (25,25,0)$
- \newline
- \STATE {//Incrémentation de $ k $ }
- \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 2$
- \newline
-
- \STATE {//Troisième itération :}
- \STATE{//Calcul du gradient de $ J $ :}
- \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (50,50,0) $
- \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 : (70, 70, 0)$
- \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
- \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (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 des 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 $ //résultat : k = 3$
- \newline
-
- \STATE {//Quatrième itération :}
- \STATE{//Calcul du gradient de $ J $ :}
- \STATE $ \nabla J(x,y,z) = (2x_k,2y_k,2z_k)$ \hfill $ //résultat : (25,25,0) $
- \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 : (45, 45, 0)$
- \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
- \newline
- \STATE {//Calcule de la direction de la pente $ d_k $ (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 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 : (6.25,6.25,0)$
- \STATE {//Incrémentation de $ k $}
- \newline
- \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 4$
- \STATE $ $
- \newline
-
- \STATE {//Cinquième itération :}
- \STATE{//Calcul 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 {//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 : (32.5, 32.5, 0)$
- \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
- \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (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 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 : (3.125,3.125,0)$
- \newline
- \STATE {//Incrémentation de $ k $}
- \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : k = 5$
- \newline
-
- \STATE {//Sixième itération :}
- \STATE{//Calcul 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 {//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 : (26.25, 26.25, 0)$
- \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
- \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (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 des 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 $ //résultat : k = 6$
- \newline
-
- \STATE {//Septième itération :}
- \STATE{//Calcul 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 {//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 : (23.125, 23.125, 0)$
- \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
- \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (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 des 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 $ //résultat : k = 7$
- \newline
-
- \STATE {//Huitième itération :}
- \STATE{//Calcul 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 {//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 : (21.5625, 21.5625, 0)$
- \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
- \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (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 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.390625,0.390625,0)$
- \newline
- \STATE {//Incrémentation de $ k $}
- \STATE $ k \leftarrow k + 1$ \hfill $ //résulat : k = 8$
- \newline
-
- \STATE {//Neuvième itération :}
- \STATE{//Calcul 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 {//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 : (20.78125, 20.78125, 0)$
- \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
- \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (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 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.1953125,0.1953125,0)$
- \newline
- \STATE {//Incrémentation de $ k $}
- \STATE $ k \leftarrow k + 1 \hfill //résultat : k = 9$
- \newline
-
- \STATE {//Dixième itération :}
- \STATE{//Calcul 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 {//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 : (20.390625, 20.390625, 0)$
- \STATE $ \varepsilon_k = \norme{\nabla L((x_k,y_k,z_k),(\lambda_1,\lambda_2))}$
- \newline
- \STATE {//Calcul de la direction de la pente $ d_k $ (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 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.097665625,0.097665625,0)$
- \newline
- \STATE {//Incrémentation de $ k $}
- \STATE $ k \leftarrow k + 1$ \hfill $ //résultat : 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}
-\end{algorithm}
+\end{algorithmic}
\bibliographystyle{plain}
\bibliography{stdlib_sbphilo}
repositories / Projet_Recherche_Operationnelle.git / blobdiff