From 7590f4bb3c2432c43c58e6f4480c03bc324d7dfc Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Tue, 6 Nov 2018 20:55:34 +0100 Subject: [PATCH] Add the example to run the SQP algorithm. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Add some definitions. Signed-off-by: Jérôme Benoit --- rapport/ProjetOptimRO.tex | 111 +++++++++++++++++++++++++++++++++----- 1 file changed, 99 insertions(+), 12 deletions(-) diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index 6ffc1f6..925282d 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -233,7 +233,11 @@ Définissons quelques notions supplémentaires de base nécessaires à la suite $ A \subset \mathbb{R}^n $ est un fermé $ \iff A = \overline{A} $. \end{Rmq} \begin{Def} - Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $. + Soient $ f : \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ S \subset \mathbb{R}^n $. On définit $ \mathrm{argmin} $ de $ f $ sur $ S $ par : + $$ \underset{x \in S}{\mathrm{argmin}} f(x) = \{ x \in \mathbb{R}^n \ | \ x \in S \land \forall y \in S \ f(y) \geq f(x) \} $$ +\end{Def} +\begin{Def} + Soient une fonction $ f : \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $. \newline On dit que $ f $ est continue en $ x^\ast $ si $$ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \exists \alpha \in \mathbb{R}_{+}^{*} \ \forall x \in \mathbb{R}^n \ \norme{x - x^\ast} \leq \alpha \implies |f(x) - f(x^\ast)| \leq \varepsilon $$ @@ -250,7 +254,7 @@ Définissons quelques notions supplémentaires de base nécessaires à la suite cette dérivée. \end{Def} \begin{Def} - Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ + Soient une fonction $ f : \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast, h \in \mathbb{R}^n $. \newline On dit que $ f $ est différentiable en $ x^\ast $ si il existe une application linéraire $ d_{x^\ast}f $ de $ \mathbb{R}^n $ dans $ \mathbb{R} $ telle que @@ -304,8 +308,8 @@ Définissons quelques notions supplémentaires de base nécessaires à la suite \subsection{Conditions d'existence d'un extremum} -On peut démontrer que $ \mathcal{C }$ est un ensemble fermé de $ \mathbb{R}^n $ si $ g $ et $ h $ sont continues. -On peut en déduire que si $ J $ est continue, $ \mathcal{C } $ est un ensemble fermé et borné de $ \mathbb{R}^n $. +On peut démontrer que $ \mathcal{C}$ est un ensemble fermé de $ \mathbb{R}^n $ si $ g $ et $ h $ sont continues. +On peut en déduire $ \mathcal{C} $ est un ensemble fermé et borné de $ \mathbb{R}^n $. \begin{Th}[Théorème de Weierstrass] Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue. \newline @@ -314,7 +318,7 @@ On peut en déduire que si $ J $ est continue, $ \mathcal{C } $ est un ensemble \newline De la même façon, il existe un maximum global de $ J $ sur $ \mathcal{C} $. \end{Th} -On en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues \cite{LJK,RON}. L'étude de la convexité de $ J $ sur $ \mathcal{C} $ permet d'explorer l'unicité de la solution \cite{LJK,RON}. +Si $ J $ est continue, on en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues \cite{LJK,RON}. L'étude de la convexité de $ J $ sur $ \mathcal{C} $ permet d'explorer l'unicité de la solution \cite{LJK,RON}. \subsection{Conditions de caractérisation d'un extremum} @@ -322,7 +326,7 @@ Dans le cas où $ J, g, h $ sont continûment différentiable et ses dérivées \newline On peut en déduire que une condition nécessaire et suffisante pour que $ x^\ast \in \mathring{\mathcal{C}} $ soit un des extremums locaux de $ J $ est que $ \nabla J(x^\ast) = 0 $. Mais si $ x^\ast \in \overline{\mathcal{C}}\setminus\mathring{\mathcal{C}} $ (la frontière de $ \mathcal{C} $) alors $ \nabla J(x^\ast) $ n'est pas nécessairement nul. Il sera par conséquent nécessaire de trouver d'autres caratérisations d'un extremum local \cite{FEA,WAL}. -\subsubsection{Conditions de Karuch-Kuhn-Tucker}\label{KKT} +\subsubsection{Conditions nécessaires de Karuch-Kuhn-Tucker ou \textit{KKT}}\label{KKT} \begin{Th} Soient $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $. @@ -336,12 +340,26 @@ On peut en déduire que une condition nécessaire et suffisante pour que $ x^\as 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 $$ 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. \end{Th} \begin{proof} Elle repose sur le lemme de Farkas \cite{FEA,RON}. \end{proof} Il est à noter que une condition d'égalité peut se répresenter par deux conditions d'inégalité : $ \forall x \in \mathbb{R}^n \ \forall i \in \{ 1,\ldots,q \} \ h_i(x) = 0 \iff h_i(x) \leq 0 \land h_i(x) \geq 0 $ \cite{FEA}, ce qui peut permettre de réécrire le problème $ \mathcal{P} $ en éliminant les contraintes d'égalités et change la forme des conditions \textit{KKT} à vérifier mais rajoute $ 2q $ conditions d'inégalités et donc $ 2q $ multiplicateurs de Kuhn-Tucker. +\begin{Def} + On appelle un point admissible $ x^\ast \in \mathcal{C} $ un point critique de $ \mathcal{P} $ si il statisfait les conditions \textit{KKT}. +\end{Def} +\subsubsection{Conditions suffisantes du deuxième ordre} + +\begin{Th} + Les conditions suffisantes en plus de celles \textit{KKT} pour que $ x^\ast \in \mathcal{C} $ soit un minimum local de $ J $ sont : + \begin{enumerate}[label=(\roman*)] + \item relâchement complémentaire dual\footnote{La définition de cette notion ne sera pas donnée car elle n'est pas nécessaire pour l'étude de la méthode PQS.} strict en $ x^\ast $. + \item $ \forall v \in \mathbb{R}^n \land v \neq 0 \ \langle H_x[L](x^\ast,\lambda,\mu)v,v \rangle > 0 $. + \end{enumerate} +\end{Th} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -459,7 +477,7 @@ Illustrées par les méthodes de descente de gradient, aucune de ces deux strat \end{Def} \begin{Def} Dans le cas où $ J $ est différentiable sur $ \mathcal{C} $, on dit que un algorithme de descente converge ssi - $$ \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$ + $$ \forall x_0 \in \mathbb{R}^n \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$ \end{Def} \subsubsection{Principe de démonstration de convergence} @@ -472,7 +490,19 @@ En sommant ces inégalités pour $ k $ variant de $ 0 $ à $ N - 1 $, on obtient $$ \forall N \in \mathbb{N} \ J(x_0) - J(x_N) \geq c \sum_{i=0}^{N-1}\norme{\nabla J(x_i)}^2 $$ Si $ J $ est bornée inférieurement, alors nécessairement $ J(x_0 ) - J(x_N) $ est majorée et donc la somme partielle est majorée, et donc la série $ (\sum\limits_{i=0}^{N-1}\norme{\nabla J(x_i)}^2)_{N \in \mathbb{N}} $ converge, ce qui implique : $$ \lim\limits_{k \rightarrow +\infty} \norme{\nabla J(x_k)} = 0 $$ -L'étude plus détaillée de différents algorithmes de descente qui utilisent différentes méthodes de recherche linéaire pour optimiser $ \varphi $ et le choix d'une direction ainsi que leurs convergences sort du cadre de ce projet. +\begin{Def} + On considère $ (x_n)_{n \in \mathbb{N}} $, la suite des itérés donnés par un algorithme convergent. On note $ x^\ast $ la limite de la suite $ (x_n)_{n \in \mathbb{N}} $ et on suppose que $ x_k \neq x^\ast $, pour tout $ k \in \mathbb{N} $. La convergence de l’algorithme est alors dite : + \begin{itemize} + \item linéaire si l'erreur décroît linéairement i.e. : + $$ \exists \tau \in ]0,1[ \ \lim_{k \rightarrow +\infty} \frac{\norme{x_{k+1} - x^\ast}}{\norme{x_k - x^\ast}} = \tau $$ + \item superlinéaire si : + $$ \lim_{k \rightarrow +\infty} \frac{\norme{x_{k+1} - x^\ast}}{\norme{x_k - x^\ast}} = 0 $$ + \item d'ordre $ p $ si : + $$ \exists \tau \geq 0 \ \lim_{k \rightarrow +\infty} \frac{\norme{x_{k+1} - x^\ast}}{\norme{x_k - x^\ast}^p} = \tau $$ + En particulier, si $ p = 2 $, la convergence est dite quadratique. + \end{itemize} +\end{Def} +L'étude plus détaillée de différents algorithmes de descente qui utilisent différentes méthodes de recherche linéaire pour optimiser $ \varphi $ ainsi que leurs convergences sort du cadre de ce projet. \section{Méthode Newtonienne} @@ -521,7 +551,7 @@ Nous ne répondrons pas à ces questions qui sont hors du cadre de ce projet. Ce \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 d’un multiplicateur en travaillant sur un problème d’optimisation déduit du problème initial par \textit{dualité}. +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{Algorithmes Newtoniens} @@ -566,7 +596,7 @@ $$ \begin{pmatrix} 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 = \begin{bmatrix} \nabla h_1(x)\ldots\nabla h_q(x) \end{bmatrix} $$ +$$ D_h(x)^\top = \begin{bmatrix} \nabla h_1(x)^\top\ldots\nabla h_q(x)^\top \end{bmatrix} $$ 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 \\ @@ -580,7 +610,7 @@ $$ \begin{pmatrix} \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 Les colonnes $ \nabla h_1(x_k)^\top,\ldots,\nabla h_q(x_k)^\top $ de $ D_h(x_k)^\top $ sont linéairement indépendants : c’est la condition première de \textit{KTT} ou condition 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 : @@ -656,8 +686,14 @@ $$ $$ où $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $, $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$ et $h: \mathbb{R}^n \longrightarrow \mathbb{R}^q$ sont supposées au moins différentiables. \newline -Selon le même principe qu’avec contraintes d’égalité seules, on linéarise les contraintes et on utilise une approximation quadratique du Lagrangien : +Selon le même principe qu’avec contraintes d’égalité seules, on linéarise les contraintes et on utilise une approximation quadratique du Lagrangien à l'aide de développements de Taylor-Young en $ x_k $ et $ (x_k,\lambda_k,\mu_k) $ respectivement : $$ L(x,\lambda,\mu) = J(x) + \lambda^\top g(x) + \mu^\top h(x), \ \lambda \in \mathbb{R}_+^p \land \mu \in \mathbb{R}^q $$ +Soit à l'ordre 2 pour le Lagrangien : +$$ L(x,\lambda,\mu) \approx L(x_k,\lambda_k,\mu_k) + \nabla L(x_k,\lambda_k,\mu_k)^\top (x - x_k) + \frac{1}{2} (x - x_k)^\top H[L](x_k,\lambda_k,\mu_k) (x - x_k) $$ +et à l'ordre 1 pour les contraintes : +$$ 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 $ : \hrulefill \newline @@ -692,6 +728,57 @@ Afin que le sous-programme quadratique $ \mathcal{PQ}_k $ admette une unique sol \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. +\subsection{Stratégie d'approximation de la hessienne} + +\subsubsection{Équation de sécante et approximation} + +L'approximation $ H_k $ de la hessienne du Lagrangien peut être obtenu par la relation : +$$ \nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1}) \approx H[L](x_{k+1},\lambda_{k+1},\mu_{k+1})(x_{k+1} - x_k) $$ +On construit une approximation $ H_{k+1} $ de $ H[L](x_{k+1},\lambda_{k+1},\mu_{k+1}) $ comme solution de l’équation : +$$ H_{k+1}(x_{k+1} - x_k) = \nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1}) $$ +appelée équation de sécante ou équation de quasi-Newton. +\newline +De façon similaire, on peut construire une approximation $ B_{k+1} $ de $ H[L](x_{k+1},\lambda_{k+1},\mu_{k+1})^{-1} $ comme solution de l’équation : +$$ B_{k+1}(\nabla L(x_{k+1},\lambda_{k+1},\mu_{k+1}) - \nabla L(x_{k},\lambda_{k+1},\mu_{k+1})) = x_{k+1} - x_k $$ +Dans les deux cas, les équations de quasi-Newton forment un système sous-déterminé à $ n $ équations et $ n^2 $ inconnues. Il existe donc une infinité de matrices $ H_{k+1} $ pouvant convenir. +\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} + +\subsection{Exemple d'utilisation de PQS} + +Considérons le problème $ \mathcal{P} $ suivant : +$$ + \mathcal{P} \left \{ + \begin{array}{l} + \displaystyle\min_{(x,y,z) \in \mathbb{R}^3} J(x,y,z) = x^2 + y^2 + z^2 -r^2 \\ + 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 \\ + \end{array} + \right . +$$ +où $$ (r,r_1,r_2) \in \mathbb{R}_+^3. $$ +Les hypothèses : $ J $ et $ g $ sont de classe $ \mathcal{C}^2 $. +\newline +Le Lagrangien de $ \mathcal(P) $ : $ L(x,y,z,\lambda) = $ +\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)) = $ +\newline +Le gradient de $ g $ : $ \nabla g(x,y,z) = (\nabla g_1(x,y,z),\nabla g_2(x,z,z)) = $ +\newline +La matrice hessienne de $ J $ : $ H[J](x,y,z) = + \begin{pmatrix} + \frac{\partial^2 J}{\partial^2 x} & \frac{\partial^2 J}{\partial x\partial y} & \frac{\partial^2 J}{\partial x\partial z} \\ + \frac{\partial^2 J}{\partial y\partial x} & \frac{\partial^2 J}{\partial^2 y} & \frac{\partial^2 J}{\partial y\partial z} \\ + \frac{\partial^2 J}{\partial z\partial x} & \frac{\partial^2 J}{\partial z\partial y} & \frac{\partial^2 J}{\partial^2 z} \\ + \end{pmatrix} = + \begin{pmatrix} + & & \\ + & & \\ + & & \\ + \end{pmatrix} $ + \bibliographystyle{plain} \bibliography{stdlib_sbphilo} -- 2.34.1