\usepackage{tocbibind}
\usepackage{lmodern}
\usepackage{enumitem}
+\usepackage{algorithm2e}
+\usepackage{algorithmic}
%%%%%Marges & en-t\^etes
$ \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}
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 $.
$$ 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 :
\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
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} $.
\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 = 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 .
\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}
+% \subsubsection{Mises à jour DFP et BFGS}
+Les méthodes de mise à jour DFP et BFGS suivent par exemple cette stratégie.
\subsection{Exemple d'utilisation de PQS}
\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 $ la précision, $ (x_0,y_0,z_0) = $ point initial et $ \lambda_0 = $ multiplicateur initial.
+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 de $ \mathcal{P} $ : $ L(x,y,z,\lambda) = $
+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 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 $ 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 $ g $ : $ \nabla g(x,y,z) = (\nabla g_1(x,y,z),\nabla g_2(x,z,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
-La matrice hessienne de $ J $ : $ H[J](x,y,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) =
\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} $.
+
+\newpage
+
+\subsection{Trace d'éxécution de l'algorithme PQS}
+
+\begin{center}
+ \includegraphics[scale=0.2]{sphere2.jpg} \\
+ \footnotesize{
+ \small \it Fig : Exemple de la sphère \\
+ \vspace*{0.5cm}
+ }
+\end{center}
+
+En utilisant le problème $ \mathcal{P} $ précédent :
+
+\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 $r_1 = r_2 = 10$.
+\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)) = 4800. $
+
+\newpage
+
+% \begin{algorithmfloat}[#Algo 1]
+\begin{algorithm}
+ \caption {Trace d'éxécution de l'algorithme PQS}
+ \begin{algorithmic}
+ \REQUIRE $g(x_0,y_0,z_0)\leq 0$, $(x_0,y_0,z_0) = (10, 10 ,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 $
+ \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 {//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}
\bibliographystyle{plain}
\bibliography{stdlib_sbphilo}
repositories / Projet_Recherche_Operationnelle.git / blobdiff