From 7fd51f8babe0b5bc1431b377bd3e2eb2c7230b04 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Sun, 4 Nov 2018 18:55:35 +0100 Subject: [PATCH] Add the maths for the SQP method. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- rapport/ProjetOptimRO.tex | 87 +++++++++++++++++++++++++++++++++++---- 1 file changed, 78 insertions(+), 9 deletions(-) diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index 5fc4678..809d31f 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -20,6 +20,7 @@ \usepackage{fancyhdr} \usepackage{tocbibind} \usepackage{lmodern} +\usepackage{enumitem} %%%%%Marges & en-t\^etes @@ -78,7 +79,7 @@ \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} \\ ~ \\ @@ -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 \{ - \begin{array}{r} + \begin{array}{l} \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} \\ - (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) $. @@ -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 -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 @@ -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} -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)} @@ -549,7 +552,7 @@ Trouver une solution d’un problème d’optimisation sous contraintes fonction \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} @@ -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 \{ - \begin{array}{r} + \begin{array}{l} \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 : -$$ \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} - \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[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} -- 2.34.1