From 682e0379e0659335de111cd95a6fc7c420588a80 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Sun, 4 Nov 2018 15:49:42 +0100 Subject: [PATCH] Begin the real work on 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 | 92 +++++++++++++++++++++++++++++++++++++-- 1 file changed, 88 insertions(+), 4 deletions(-) diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index f206114..5fc4678 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -42,7 +42,7 @@ \newtheorem{Cor}[Th]{Corollaire} \newtheorem{Rmq}{Remarque} -\newcommand{\norme}[1]{\left\Vert #1\right\Vert} +\newcommand{\norme}[1]{\left\Vert #1 \right\Vert} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -206,6 +206,15 @@ Si la modélisation de la problèmatique $ \mathcal{P} $ est considérée comme \subsection{Quelques définitions annexes} Définissons quelques notions supplémentaires de base nécessaires à la suite : +\begin{Def} + 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) \\ + & & 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) $. +\end{Def} \begin{Def} Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $. \newline @@ -281,11 +290,16 @@ Définissons quelques notions supplémentaires de base nécessaires à la suite \begin{Prop} \begin{enumerate} \item $ H[f](x^\ast) $ est une matrice symétrique (Théorème de symétrie de Schwarz). - \item On a le développement de Taylor-Young à l'ordre 2 suivant : + \item On a le développement de Taylor-Young à l'ordre 2 en $ x^\ast $ suivant : $$ f(x^\ast + v) = f(x^\ast) + \langle \nabla f(x^\ast),v \rangle + \frac{1}{2} v^\top H[f](x^\ast) v + \varepsilon(v) $$ + ou + $$ f(x^\ast + v) = f(x^\ast) + \langle \nabla f(x^\ast),v \rangle + \frac{1}{2} \langle H[f](x^\ast)v,v \rangle + \varepsilon(v) $$ avec $ \frac{|\varepsilon(v)|}{\norme{v}} \rightarrow 0 $ quand $ \norme{v} \rightarrow 0 $. \end{enumerate} \end{Prop} +\begin{proof} + Elle repose entièrement sur deux autres théorèmes dont les preuves sont connues et de la réécriture de formulation de résultat. +\end{proof} \subsection{Conditions d'existence d'un extremum} @@ -338,6 +352,8 @@ Dans ce projet, nous nous proposons d'étudier une des méthodes d'optimisation \section{Methode de descente}\label{descente} +Nous supposons que le domaine des contraintes de $ \mathcal{P} $ est un ouvert de $ \mathbb{R}^n $ (c'est à dire que nous n'avons pas de contraintes) et $ J $ est une fonction définie sur $ \mathbb{R}^n $ à valeurs réelles supposée différentiable, voire même deux fois différentiable. Les conditions nécessaires d’optimalité du premier et du second ordre expriment le fait qu’il n’est pas possible de “descendre” à partir d’un point de minimum (local ou global). Cette observation va servir de point de départ à l’élaboration des méthodes dites de descente. + Partant d’un point $ x_0 \in \mathbb{R}^n $ arbitrairement choisi, un algorithme de descente va chercher à générer une suite d’itérés $ (x_k)_{k \in \mathbb{N}} $ de $ \mathbb{R}^n $ définie par : $$ x_{k+1} = x_k + s_kd_k $$ où $ s_k \in \mathbb{R}_{+}^{*},d_k \in \mathbb{R}^n $ et avec $$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$ @@ -479,7 +495,7 @@ L'étude plus détaillée de différents algorithmes de descente qui utilisent d \section{Méthode Newtonienne} -L’algorithme de Newton en optimisation est une application directe de l’algorithme de +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, $$ @@ -487,10 +503,78 @@ 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. +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 $. +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 : + +\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 de rendre compte de la filiation entre la méthode PQS et celle Newtonienne. \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é}. + +\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} $. + +\subsection{Algorithme PQS} + +\subsubsection{Contraintes d’égalité} + +Considérons un problème d’optimisation différentiable $ \mathcal{P} $ avec contraintes d’égalité : +$$ + \mathcal{P} \left \{ + \begin{array}{r} + \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\ + h(x) = 0 + \end{array} + \right . +$$ +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 $$ +donc $ \mathcal{P} $ devient : +$$ \begin{pmatrix} + \nabla J(x) + \sum\limits_{i=0}^{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 : + \bibliographystyle{plain} \bibliography{stdlib_sbphilo} -- 2.34.1