Add the maths for the SQP method.

Signed-off-by: Jérôme Benoit <jerome.benoit@piment-noir.org>

diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex
index 5fc46789a49c4b96753207832f6d584458b1e374..809d31f4c0ab17d8c642c82f8b2ba6e4a24d9683 100644 (file)
--- a/rapport/ProjetOptimRO.tex
+++ b/rapport/ProjetOptimRO.tex
@@ -20,6 +20,7 @@
 \usepackage{fancyhdr}
 \usepackage{tocbibind}
 \usepackage{lmodern}
 \usepackage{fancyhdr}
 \usepackage{tocbibind}
 \usepackage{lmodern}

+\usepackage{enumitem}

 
 
 %%%%%Marges & en-t\^etes
 
 
 %%%%%Marges & en-t\^etes


@@ -78,7 +79,7 @@
  \begin{tabular}{c}
   \hline
   ~                                                             \\
  \begin{tabular}{c}
   \hline
   ~                                                             \\

-  \LARGE\textbf {Programmation Séquentielle Quadratique ou PQS} \\
+  \LARGE\textbf {Programmation Quadratique Séquentielle ou PQS} \\

   \LARGE\textbf {en}                                            \\
   \LARGE\textbf {Optimisation non linéraire sous contraintes}   \\
   ~                                                             \\
   \LARGE\textbf {en}                                            \\
   \LARGE\textbf {Optimisation non linéraire sous contraintes}   \\
   ~                                                             \\


@@ -181,7 +182,7 @@ Définissons le problème central $ \mathcal{P} $ que se propose de résoudre la
  La problèmatique $ \mathcal{P} $ se définit par :
  $$
   \mathcal{P} \left \{
  La problèmatique $ \mathcal{P} $ se définit par :
  $$
   \mathcal{P} \left \{

-  \begin{array}{r}
+  \begin{array}{l}

    \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
    g(x) \leq 0                                 \\
    h(x) = 0
    \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
    g(x) \leq 0                                 \\
    h(x) = 0


@@ -210,7 +211,7 @@ Définissons quelques notions supplémentaires de base nécessaires à la suite
  On définit le Lagrangien associé à $ \mathcal{P} $ par :
  $$ \begin{array}{r c l}
    L : \mathbb{R}^n \times \mathbb{R}^q \times \mathbb{R}_+^p & \longrightarrow & \mathbb{R}                                                                                                      \\
  On définit le Lagrangien associé à $ \mathcal{P} $ par :
  $$ \begin{array}{r c l}
    L : \mathbb{R}^n \times \mathbb{R}^q \times \mathbb{R}_+^p & \longrightarrow & \mathbb{R}                                                                                                      \\

-   (x,\lambda,\mu)                                            & \longmapsto     & L(x,\lambda,\mu) = J(x) + \sum\limits_{i=0}^{q} \lambda_i h_i(x) + \sum\limits_{j=0}^{p} \mu_j g_j(x)           \\
+   (x,\lambda,\mu)                                            & \longmapsto     & L(x,\lambda,\mu) = J(x) + \sum\limits_{i=1}^{q} \lambda_i h_i(x) + \sum\limits_{j=1}^{p} \mu_j g_j(x)           \\

                                                               &                 & L(x,\lambda,\mu) = J(x) + \langle \lambda,h(x) \rangle_{\mathbb{R}^q} + \langle \mu,g(x) \rangle_{\mathbb{R}^p}
   \end{array} $$
  où l’on note $ \lambda $  et $ \mu $ les vecteurs de coordonnées respectives $ (\lambda_1,\ldots,\lambda_q) $ et $ (\mu_1,\ldots,\mu_p) $.
                                                               &                 & L(x,\lambda,\mu) = J(x) + \langle \lambda,h(x) \rangle_{\mathbb{R}^q} + \langle \mu,g(x) \rangle_{\mathbb{R}^p}
   \end{array} $$
  où l’on note $ \lambda $  et $ \mu $ les vecteurs de coordonnées respectives $ (\lambda_1,\ldots,\lambda_q) $ et $ (\mu_1,\ldots,\mu_p) $.


@@ -508,7 +509,9 @@ $$ \underset{d \in \mathbb{R}^n}{\mathrm{argmin}} \ J(x_k) + \langle \nabla J(x_
 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 $.
 A condition que la matrice $ H[J](x_k) $ soit définie positive à chaque itération, la méthode
 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 $.
 A 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 $ . Les propriétés remarquables de cet algorithme sont :
+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
 
 \begin{tabular}{|p{20em}|p{20em}|}
  \hline


@@ -539,7 +542,7 @@ Plusieurs questions se posent alors :
  \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}
  \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 de rendre compte de la filiation entre la méthode PQS et celle Newtonienne.
+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)}
 
 
 \section{Méthode PQS (ou SQP)}
 


@@ -549,7 +552,7 @@ Trouver une solution d’un problème d’optimisation sous contraintes fonction
 
 \subsection{Algorithmes newtoniens}
 
 
 \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 géométrique duale $ (\lambda^k)_{k \in \mathbb{N}} $ de multiplicateurs convergeant vers un multiplicateur optimal $ \overline{\lambda} $ 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}} $ de multiplicateurs convergeant vers un multiplicateur optimal $ \overline{\lambda} $ associé à $ \overline{x} $.

 
 \subsection{Algorithme PQS}
 
 
 \subsection{Algorithme PQS}
 


@@ -558,7 +561,7 @@ Les algorithmes newtoniens sont basés sur la linéarisation d’équations cara
 Considérons un problème d’optimisation différentiable $ \mathcal{P} $ avec contraintes d’égalité :
 $$
  \mathcal{P} \left \{
 Considérons un problème d’optimisation différentiable $ \mathcal{P} $ avec contraintes d’égalité :
 $$
  \mathcal{P} \left \{

- \begin{array}{r}
+ \begin{array}{l}

   \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
   h(x) = 0
  \end{array}
   \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\
   h(x) = 0
  \end{array}


@@ -567,13 +570,79 @@ $$
 où $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$ sont supposées au moins différentiables.
 \newline
 Les conditions d’optimalité de Lagrange (ou \textit{KKT}) s’écrivent :
 où $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$ sont supposées au moins différentiables.
 \newline
 Les conditions d’optimalité de Lagrange (ou \textit{KKT}) s’écrivent :

-$$ \nabla L(x,\lambda) = 0 \iff \nabla J(x) + \sum\limits_{i=0}^{q} \lambda_i \nabla h_i(x) = 0 $$
+$$ \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}
 donc $ \mathcal{P} $ devient :
 $$ \begin{pmatrix}

- \nabla J(x) + \sum\limits_{i=0}^{q} \lambda_i \nabla h_i(x) \\
+ \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(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 \\
+  \lambda_{k+1} - \lambda_k
+ \end{pmatrix} = -\nabla L(x_k,\lambda_k) $$
+soit :
+$$ \begin{pmatrix}
+  H_x[L](x_k,\lambda_k) & D_h(x_k)^\top \\
+  D_h(x_k)              & 0
+ \end{pmatrix} \begin{pmatrix}
+  x_{k+1} - x_k \\
+  \lambda_{k+1} - \lambda_k
+ \end{pmatrix} = -\begin{pmatrix}
+  \nabla_x L(x_k,\lambda_k) \\
+  h(x_k)
+ \end{pmatrix}  $$
+où $ D_h(x) $ désigne la matrice jacobienne de l’application $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ définie par :
+$$ D_h(x)^\top = [\nabla h_1(x)\ldots\nabla h_q(x)] $$
+Posons : $ H_k = H_x[L](x_k,\lambda_k), \ d = x_{k+1} - x_k $ et $ \mu = \lambda_{k+1} $. L'itération s'écrit donc :
+$$ \begin{pmatrix}
+  H_k      & D_h(x_k)^\top \\
+  D_h(x_k) & 0
+ \end{pmatrix} \begin{pmatrix}
+  d \\
+  \mu - \lambda_k
+ \end{pmatrix} = -\begin{pmatrix}
+  \nabla_x L(x_k,\lambda_k) \\
+  h(x_k)
+ \end{pmatrix} $$
+et est bien définie à condition que la matrice $ H_x[L](x_k,\lambda_k) $ soit inversible. Ce sera le cas si :
+\begin{enumerate}[label=(\roman*)]
+ \item Les colonnes $ \nabla h_1(x_k),\ldots,\nabla h_q(x_k) $ de $ D_h(x_k)^\top $ sont linéairement indépendants : c’est l’hypothèse de qualification des contraintes.
+ \item Quel que soit $ d \neq 0 $ tel que $ D_h(x_k)d = 0, \ d^\top H_k d > 0 $ : c’est la condition suffisante d’optimalité du second ordre dans le cas de contraintes d’égalité.
+\end{enumerate}
+Revenons à l’itération. Elle s’écrit encore :
+$$
+ \left \{
+ \begin{array}{r c l}
+  H_kd + \sum\limits_{i=1}^q(\mu_i - \lambda_{k_i})\nabla h_i(x_k) & = & -\nabla_x L(x_k,\lambda_k)        \\
+  \nabla h_i(x_k)^\top d + h_i(x_k)                                & = & 0, \ \forall i \in \{1,\ldots,q\}
+ \end{array}
+ \right .
+$$
+Or $ \nabla_x L(x_k,\lambda_k) =  \nabla J(x_k) + \sum\limits_{i=1}^{q} \lambda_{k_i} \nabla h_i(x_k) $, d'où :
+$$
+ \left \{
+ \begin{array}{r c l}
+  H_kd + \sum\limits_{i=1}^q\mu_i\nabla h_i(x_k) & = & -\nabla J(x_k)                    \\
+  \nabla h_i(x_k)^\top d + h_i(x_k)              & = & 0, \ \forall i \in \{1,\ldots,q\}
+ \end{array}
+ \right .
+$$
+On reconnait dans le système ci-dessus les conditions d’optimalité de Lagrange du
+problème quadratique suivant :
+$$
+ \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 \\
+  h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
+ \end{array}
+ \right .
+$$
+Le problème $ \mathcal{PQ}_k $ peut être vu comme la minimisation d’une approximation quadratique du Lagrangien de $ \mathcal{P} $ avec une approximation linéaire des contraintes.
+\newline
+Comme son nom l’indique, la méthode PQS consiste à remplacer le problème initial par une suite de problèmes quadratiques sous contraintes linéaires plus faciles à résoudre. L’algorithme est le suivant :
+
+\subsubsection{Contraintes d’inégalité}

 
 \bibliographystyle{plain}
 \bibliography{stdlib_sbphilo}
 
 \bibliographystyle{plain}
 \bibliography{stdlib_sbphilo}