From: Jérôme Benoit Date: Sun, 4 Nov 2018 20:51:36 +0000 (+0100) Subject: Add SQP algorithms. X-Git-Url: https://git.piment-noir.org/?p=Projet_Recherche_Operationnelle.git;a=commitdiff_plain;h=e17152e0b05429858eeacdf123e34d354cc167d1 Add SQP algorithms. Signed-off-by: Jérôme Benoit --- diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index 809d31f..affb198 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -377,8 +377,7 @@ tions. \begin{proof} Elle s'effectue en utilisant le développement de Taylor-Young de l’application $ t \longmapsto f(x_0 + td) $ à l’ordre 1. \end{proof} -Cette dernière inégalité garantit une décroissance minimum de la fonction $ J $ dans la -direction $ d $ et peut se traduire par : la décroissance de la fonction $ J $, en effectuant un pas de longueur $ t $ dans la direction $ d $ , est au moins égale à la longueur du pas multipliée par une fraction de la pente. Le schéma général d’un algorithme de descente est alors le suivant : +Cette dernière inégalité garantit une décroissance minimum de la fonction $ J $ dans la direction $ d $ et peut se traduire par : la décroissance de la fonction $ J $, en effectuant un pas de longueur $ t $ dans la direction $ d $ , est au moins égale à la longueur du pas multipliée par une fraction de la pente. Le schéma général d’un algorithme de descente est alors le suivant : \hrulefill \newline @@ -386,9 +385,9 @@ ALGORITHME DE DESCENTE MODÈLE. \newline \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire. \newline -\textit{Sortie}: une approximation de la solution du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $. +\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $. \begin{enumerate} - \item $ k := 0 $ + \item $ k := 0 $. \item Tant que "test d’arrêt" non satisfait, \begin{enumerate} \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $. @@ -402,9 +401,7 @@ ALGORITHME DE DESCENTE MODÈLE. \subsection{Choix de la direction de descente} -Une fois la théorie bien maîtrisée, calculer une direction de descente est relativement -simple. Dans le cas différentiable, il existe deux grandes stratégies de choix de direction de -descente : +Une fois la théorie bien maîtrisée, calculer une direction de descente est relativement simple. Dans le cas différentiable, il existe deux grandes stratégies de choix de direction de descente : \begin{itemize} \item la stratégie de Cauchy : $ d_k = -\nabla J(x_k) $, conduisant aux \textit{algorithmes de gradient}. \item la stratégie de Newton : $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $, conduisant aux \textit{algorithmes Newtoniens}. @@ -424,8 +421,7 @@ sans contrainte, on testera si $$ \norme{\nabla J(x_k)} < \varepsilon, $$ auquel cas l’algorithme s’arrête et fournit l’itéré courant $ x_k $ comme solution. -En pratique, le test d’optimalité n’est pas toujours satisfait et on devra faire appel à -d’autres critères fondés sur l’expérience du numérique : +En pratique, le test d’optimalité n’est pas toujours satisfait et on devra faire appel à d’autres critères fondés sur l’expérience du numérique : \begin{itemize} \item Stagnation de la solution : $ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $. \item Stagnation de la valeur courante : $ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $. @@ -482,11 +478,9 @@ acceptables et ceux qui ne le sont pas. \subsubsection{Principe de démonstration de convergence} -Une technique classique en optimisation pour obtenir des résultats de convergence glo- -bale consiste à montrer que l’algorithme de descente considéré vérifie une inégalité du -type : +Une technique classique en optimisation pour obtenir des résultats de convergence globale consiste à montrer que l’algorithme de descente considéré vérifie une inégalité du type : $$ J(x_k) - J(x_{k+1}) \geq c\norme{\nabla J(x_k)}^2, $$ -où $ c $ est un constante réelle. +où $ c $ est une constante réelle. \newline 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 $$ @@ -496,9 +490,7 @@ L'étude plus détaillée de différents algorithmes de descente qui utilisent d \section{Méthode Newtonienne} -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 : +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 @@ -506,10 +498,8 @@ En supposant $ J $ de classe $ \mathcal{C}^2 $ et la matrice hessienne $ H[J](x_ $$ 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 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 $. +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 $. \newline Les propriétés remarquables de cet algorithme sont : @@ -547,8 +537,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é}. +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} @@ -593,7 +582,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 = [\nabla h_1(x)\ldots\nabla h_q(x)] $$ +$$ D_h(x)^\top = \begin{bmatrix} \nabla h_1(x)\ldots\nabla h_q(x) \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 \\ @@ -619,7 +608,7 @@ $$ \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ù : +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} @@ -642,8 +631,84 @@ Le problème $ \mathcal{PQ}_k $ peut être vu comme la minimisation d’une appr \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 : +\hrulefill +\newline +ALGORITHME SQP AVEC CONSTRAINTES D'ÉGALITÉ. +\newline +\textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $, $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ différentiables, $ x_0 \in \mathbb{R}^n $ point initial arbitraire, $ \lambda_0 \in \mathbb{R}^q $ multiplicateur initial, $ \varepsilon > 0 $ précision demandée. +\newline +\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $. +\begin{enumerate} + \item $ k := 0 $. + \item Tant que $ \norme{\nabla L(x_k,\lambda_k)} > \varepsilon $, + \begin{enumerate} + \item Résoudre le sous-problème quadratique : + $$ + \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 . + $$ + et obtenir la solution primale $ d_k $ et le multiplicateur $ \lambda^{\prime} $ associé à la contrainte d’égalité. + \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ k := k + 1 $. + \end{enumerate} + \item Retourner $ x_k $. +\end{enumerate} + +\hrulefill + \subsubsection{Contraintes d’inégalité} +Intéressons nous maintenant aux problèmes avec contraintes d’égalité et d’inégalité : +$$ + \mathcal{P} \left \{ + \begin{array}{l} + \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\ + g(x) \leq 0 \\ + h(x) = 0 + \end{array} + \right . +$$ +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 : +$$ 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 $$ + +\hrulefill +\newline +ALGORITHME SQP AVEC CONSTRAINTES D'ÉGALITÉ ET D'INEGALITÉ. +\newline +\textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $, $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$, $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ différentiables, $ x_0 \in \mathbb{R}^n $ point initial arbitraire, $ \lambda_0 \in \mathbb{R}_+^p $ et $ \mu_0 \in \mathbb{R}_+^q $ multiplicateurs initiaux, $ \varepsilon > 0 $ précision demandée. +\newline +\textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $. +\begin{enumerate} + \item $ k := 0 $. + \item Tant que $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $, + \begin{enumerate} + \item Résoudre le sous-problème quadratique : + $$ + \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 \\ + g_j(x_k) + \nabla g_j(x_k)^\top d = 0, \ \forall j \in \{1,\ldots,p\} \\ + h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\} + \end{array} + \right . + $$ + et obtenir la solution primale $ d_k $ et les multiplicateurs $ \lambda^{\prime} $ et $ \mu^{\prime} $ associé aux contraintes d’inégalité et d’égalité respectivement. + \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ \mu_{k+1} = \mu^{\prime}; \ k := k + 1 $. + \end{enumerate} + \item Retourner $ x_k $. +\end{enumerate} + +\hrulefill +\newline +Afin que le sous-programme quadratique $ \mathcal{PQ}_k $ admette une unique solution, la plupart des implémentations actuelles de PQS utilisent une approximation du hessien $ H_k $ du Lagrangien qui soit définie positive, en particulier celle fournie par les techniques quasi-newtonienne (BFGS) par exemple. +\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. + \bibliographystyle{plain} \bibliography{stdlib_sbphilo}