+Les hypothèses sur $ \mathcal{P} $ de la section précédente restent les mêmes dans cette section. L’algorithme de Newton en optimisation est une application directe de l’algorithme de Newton pour la résolution d’équations du type : $ F(x) = 0 $. En optimisation sans contrainte, l’algorithme de Newton cherche les solutions de l’équation :
+$$ \nabla J(x) = 0, $$
+autrement dit, les points critiques de la fonction $ J $ à minimiser.
+\newline
+En supposant $ J $ de classe $ \mathcal{C}^2 $ et la matrice hessienne $ H[J](x_k) $ inversible, une itération de l’algorithme de Newton s’écrit :
+$$ 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 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 :
+
+\begin{tabular}{|p{20em}|p{20em}|}
+ \hline
+ Avantages & Inconvénients \\
+ \hline
+ sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). & \\
+ \hline
+ & les difficultés et le coût de calcul de la hessienne $ H[J](x_k) $ : l’expression analytique des dérivées secondes est rarement disponible dans les applications. \\
+ \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. \\
+ \hline
+ & pas de distinction entre minima, maxima et points stationnaires. \\
+ \hline
+\end{tabular}
+\newline
+La question que l’on se pose est donc : comment forcer la convergence globale de l’algorithme de Newton ? L’idée des méthodes de type Newton consiste à reprendre l’algorithme de Newton en remplaçant les itérations par :
+$$ x_{k+1} = x_k - s_k H_k^{-1} \nabla J(x_k), $$
+où
+\begin{itemize}
+ \item la matrice $ H_k $ est une approximation de la hessienne $ H[J](x_k) $.
+ \item $ s_k > 0 $ est le pas calculé par une recherche linéaire bien choisie.
+\end{itemize}
+Plusieurs questions se posent alors :
+\begin{itemize}
+ \item Comment déterminer une matrice $ H_k $ qui soit une “bonne” approximation de la hessienne à l’itération $ k $ sans utiliser les informations de second ordre et garantir que $ H_k^{-1} \nabla J(x_k) $ soit bien une direction de descente de $ J $ en $ x_k $, sachant que la direction de Newton, si elle existe, n’en est pas nécessairement une ?
+ \item Comment conserver les bonnes propriétés de l’algorithme de Newton ?
+\end{itemize}
+Nous ne répondrons pas à ces questions qui sont hors du cadre de ce projet. Cette section permet d'introduire certains prérequis pour l'étude de la méthode PQS et de rendre compte de sa filiation.
+
+\section{Méthode PQS (ou SQP)}
+
+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 $$
+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{Méthode des points intérieurs}
+
+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.