Voir la source de Optimisation quadratique successive

L''''optimisation quadratique successive''' est un [[algorithme]] de résolution d'un problème d'[[optimisation non linéaire]]. Un tel problème consiste à déterminer des paramètres qui minimisent une fonction, tout en respectant des contraintes d'égalité et d'inégalité sur ces paramètres. On parle aussi de l''''algorithme OQS''' pour Optimisation Quadratique Successive ou de l''''algorithme SQP''' pour ''Sequential Quadratic Programming'', en anglais.

C'est un [[Algorithme de Newton|algorithme newtonien]] appliqué aux [[Conditions d'optimalité (dimension finie)|conditions d'optimalité]] du premier ordre du problème. Plus précisément, on peut le voir comme un [[algorithme de Josephy-Newton]] appliqué à ces conditions d'optimalité, écrites comme un problème d'[[inclusion fonctionnelle]] ou comme un problème de [[complémentarité]]. De ce fait, l'algorithme bénéficie d'une convergence locale rapide, mais chaque [[itération]] pourra demander beaucoup de temps de calcul (c'est surtout vrai dans les premières itérations). Par ailleurs, l'algorithme ne fait pas de distinction entre minima et maxima (comme l'algorithme de Newton pour minimiser une fonction sans contrainte), mais ses itérés sont attirés par tout point stationnaire «régulier». L'algorithme se ''globalise'' facilement, ce qui veut dire que l'on connait des techniques permettant la plupart du temps de forcer la convergence des itérés, même si le premier itéré n'est pas proche d'une solution du problème d'optimisation.

L'algorithme requiert que les fonctions définissant le problème d'optimisation soient «suffisamment» différentiables. Il se définit naturellement en utilisant les dérivées secondes des fonctions définissant le problème, mais il se décline aussi sous une forme quasi-newtonienne, qui ne requiert donc que l'évaluation des dérivées premières.

'''Connaissances supposées''' : le [[Différentielle|calcul différentiel]] (on linéarise des fonctions) et les [[Conditions d'optimalité (dimension finie)#Conditions de Karush, Kuhn et Tucker (KKT)|conditions d'optimalité des problèmes d'optimisation avec contraintes]] (qui est le système linéarisé) ; l'approche utilisée pour introduire l'algorithme sera mieux comprise si l'on a pris connaissance auparavant de l'[[algorithme de Josephy-Newton]], mais ce dernier point n'est pas essentiel ; bien sûr, l'algorithme a un lien étroit avec l'[[algorithme de Newton]].

== Définition de l'algorithme ==

=== Le problème à résoudre ===

L'optimisation quadratique successive est un algorithme conçu pour minimiser une fonction différentiable en présence de contraintes d'égalité et d'inégalité. Un modèle suffisamment général de ce problème peut s'écrire sous la forme suivante
<center>
<math>
(P_{EI}) \quad \left\{ \begin{array}{l}
\inf_x\,  f(x) \\
c_i (x) = 0, \quad i \in E \\
c_i(x) \leqslant 0, \quad i \in I,
\end{array} \right.
</math>
</center>
où le critère <math>f:\mathbb{E}\to\mathbb{R}</math> est défini sur un [[espace euclidien]] <math>\mathbb{E}</math>, ainsi que les fonctions <math>c_i:\mathbb{E}\to\mathbb{R}</math>, que l'on appelle contraintes. Le [[produit scalaire]] de l'espace euclidien <math>\mathbb{E}</math> est noté <math>\langle\cdot,\cdot\rangle</math>. Les contraintes sont en nombre fini, repérées par des [[Ensemble fini|ensembles finis]] d'indices <math>E</math> et <math>I</math>, dont le [[Cardinalité (mathématiques)|cardinal]] est noté
<center>
<math>m_E:=|E| \qquad\mbox{et}\qquad m_I:=|I| </math>.
</center>
Le nombre total de contraintes est noté <math>m:=m_E+m_I</math>. Les inégalités vectorielles, comme <math>c_I(x)\leqslant0</math>, doivent se comprendre composante par composante : <math>c_i(x)\leqslant0</math> pour tout <math>i\in I</math>.

Il est commode de supposer que les ensembles d'indices <math>E</math> et <math>I</math> forment une [[Partition (mathématiques)|partition]] de l'ensemble des <math>m</math> premiers entiers <math>[1:m]</math> :
<center>
<math>
E \cup I=[1:m] \qquad\mbox{et}\qquad E \cap I = \varnothing.
</math>
</center>
Si <math>v\in \mathbb{R}^m</math>, on note <math>v_E</math> le vecteur de <math>\mathbb{R}^{m_E}</math> formé des composantes <math>v_i</math> de <math>v</math> avec <math>i\in E</math>. De même pour <math>v_I</math>. On peut alors rassembler les fonctions réelles <math>c_i</math> en une seule fonction <math>c:\mathbb{E}\to\mathbb{R}^m</math>, dont les composantes <math>c_E</math> et <math>c_I</math> sont utilisées pour définir les contraintes d'égalité et d'inégalité. Pour un vecteur <math>v\in\R^m</math>, on définit <math>v^\#\in\R^m</math> par
<center><math>
[v^\#]_i=
\left\{\begin{array}{ll}
v_i & \mbox{si}~ i\in E \\
v_i^+:=\max(0,v_i) & \mbox{si}~ i\in I.
\end{array}\right.
</math></center>

On rappelle que le ''lagrangien'' du problème <math>(P_{EI})</math> est la fonction <math>\ell : \mathbb{E} \times \R^m \to \R</math> définie en <math>(x,\lambda)\in \mathbb{E} \times \R^m</math> par
<center>
<math>
\ell (x,\lambda) := f(x) + \lambda^{\!\top\!}c(x)= f(x) + \sum_{i=1}^m\lambda_ic_i(x).
</math>
</center>
Le vecteur <math>\lambda</math> porte le nom de '''multiplicateur''' (de Karush, Kuhn et Tucker ou de Lagrange) ou '''variable duale'''.

=== L'algorithme OQS ===

L'algorithme OQS est une méthode primale-duale de résolution de <math>(P_{EI})</math> procédant par linéarisation des conditions d'optimalité du premier ordre de ce problème, celles de [[Conditions d'optimalité (dimension finie)#cn1-KKT|Karush, Kuhn et Tucker (KKT)]]. L'algorithme OQS peut être vu comme l'[[algorithme de Josephy-Newton]] appliqué au système d'optimalité écrit sous la forme de [[Inclusion fonctionnelle#Contraintes d'égalité et d'inégalité|problème d'inclusion fonctionnelle]], même si ce dernier a été conçu après l'introduction de l'algorithme OQS, comme une généralisation élégante de celui-ci. L'algorithme OQS est primal-dual car il génère une suite de couples <math>(x_k,\lambda_k)\in\mathbb{E}\times\R^m</math>, où <math>x_k</math> approche une solution <math>x_*</math> de <math>(P_{EI})</math> (dite ''solution primale'' car appartenant à <math>\mathbb{E}</math>) et <math>\lambda_k</math> approche un multiplicateur optimal <math>\lambda_*\in\R^m</math> de <math>(P_{EI})</math> (aussi appelé ''solution duale'').

==== Conception de l'algorithme OQS ====

On peut énoncer l'algorithme OQS sans explication sur sa conception et c'est souvent comme cela qu'il est présenté, mais nous préférons l'introduire ici comme une application de l'[[algorithme de Josephy-Newton]] aux [[Conditions d'optimalité (dimension finie)#Conditions de Karush, Kuhn et Tucker (KKT)|conditions d'optimalité du premier ordre]] ou conditions de Karush, Kuhn et Tucker (KKT) de <math>(P_{EI})</math>. C'est aussi en adoptant ce point de vue que l'on obtient les meilleurs résultats de convergence.

Les [[Conditions d'optimalité (dimension finie)#Conditions de Karush, Kuhn et Tucker (KKT)|conditions d'optimalité de KKT]] s'écrivent en une solution <math>x_*\in\mathbb{E}</math> : il existe un ''multiplicateur optimal'' <math>\lambda_*\in\R^m</math> tel que
<center><math>
(\mbox{KKT})\quad
\left\{\begin{array}{l}
\nabla f(x_*) + c'(x_*)^* \lambda_* = 0 \\
c_E(x_*) = 0 \\
0 \leqslant (\lambda_*)_I \perp c_I(x_*) \leqslant 0.
\end{array} \right.
</math></center>
Dans ce système, <math>c'(x_*)^*:\R^m\to\mathbb{E}</math> est l'opérateur adjoint de l'opérateur linéaire dérivée <math>c'(x_*):\mathbb{E}\to\R^m</math> et la dernière identité signifie que <math>(\lambda_*)_I\geqslant0</math> (positivité des multiplicateurs optimaux associés aux contraintes d'inégalité), que <math>c_I(x_*) \leqslant 0</math> (satisfaction des contraintes d'inégalité) et que <math>(\lambda_*)_I^\mathsf{T}c_I(x_*)=0</math> (complémentarité). Ce système d'optimalité en <math>z_*:=(x_*,\lambda_*)</math> s'écrit aussi comme l'[[inclusion fonctionnelle]]
<center><math>
F(z_*)+\operatorname{N}_K(z_*)\ni0
</math></center>
dans laquelle la fonction <math>F:\mathbb{E}\times\R^m\to\mathbb{E}\times\R^m</math> est définie en <math>z=(x,\lambda)</math> par
<center><math>
F(z)=
\begin{pmatrix}
\nabla_x\ell(x,\lambda) \\ -c(x)
\end{pmatrix}
</math></center>
et <math>\operatorname{N}_K(z)</math> est le [[cône normal]] en <math>z</math> au cône [[ensemble convexe|convexe]] polyédrique <math>K:=\mathbb{E}\times(\R^{m_E}\times\R^{m_I}_+)</math>. La nature convexe conique de <math>K</math> implique que l'[[inclusion fonctionnelle]] ci-dessus s'écrit aussi sous la forme du problème de [[complémentarité]] non linéaire suivant
<center><math>
K \ni z_* \perp F(x_*) \in K^+,
</math></center>
où <math>K^+</math> est le [[cône dual]] de <math>K</math>. On voit alors aisément l'équivalence de ce système avec (KKT) en notant que <math>K^+:=\{0_\mathbb{E}\}\times(\{0_{\R^{m_E}}\}\times\R^{m_I}_+)</math>.

L'[[algorithme de Josephy-Newton]] sur les représentations de (KKT) données ci-dessus (problèmes d'inclusion fonctionnelle ou de complémentarité) calcule l'itéré suivant <math>z_{k+1}:=(x_{k+1},\lambda_{k+1})</math> à partir de l'itéré courant <math>z_k:=(x_k,\lambda_k)</math> comme solution (si une telle solution existe) de l'équation ''linéarisée'' (en réalité, on ne linéarise que <math>F</math>) :
<center><math>
F(z_k)+F'(z_k)(z-z_k)\operatorname{N}_K(z)\ni0
\quad\mbox{ou}\quad
K \ni z \perp F(z_k)+F'(z_k)(z-z_k) \in K^+.
</math></center>
Si l'on note <math>(d_k,\mu_k):=z_{k+1}-z_k=(x_{k+1}-x_k,\lambda_{k+1}-\lambda_k)</math> on obtient le système de [[complémentarité linéaire]] suivant à résoudre
<center><math>
\left\{\begin{array}{l}
\nabla f(x_k)+L_k d_k+c'(x_k)^*\lambda_{k+1} = 0 \\
c_E(x_k)+c_E'(x_k)d_k = 0 \\
0 \leqslant (\lambda_{k+1})_I \perp c_I(x_k)+c_I'(x_k)d_k \leqslant 0,
\end{array}\right.
</math></center>
où <math>L_k</math> est la hessienne <math>\nabla^2_{xx}\ell(x_k,\lambda_k)</math> du lagrangien <math>\ell</math> par rapport à <math>x</math> (voir ci-dessus).

La résolution de ce système en <math>(d_k,\lambda_{k+1})</math> (<math>\lambda_k</math> est «caché» dans <math>L_k</math>) n'est pas aisée. De plus on n'y voit plus le problème d'optimisation original. L'observation cruciale, aisée a posteriori, est de constater que ce système est formé des conditions d'optimalité de KKT du problème quadratique en <math>d\in\R^n</math> suivant
<center><math>
(\mbox{PQO})\quad
\left\{\begin{array}{l}
\inf_d\,\langle\nabla f(x_k),d\rangle + \frac{1}{2}\,\langle L_kd,d\rangle \\
c_E (x_k) + c_E'(x_k)d = 0 \\
c_I (x_k) + c_I'(x_k)d \leqslant 0.
\end{array} \right.
</math></center>
Celui-ci porte le nom de '''problème quadratique osculateur''' du problème <math>(P_{EI})</math>. Si <math>(d_k,\lambda_k^{\text{PQ}})\in\mathbb{E}\times\R^m</math> est une solution primale-duale, le nouvel itéré sera
<center><math>
x_{k+1}=x_k+d_k
\quad\mbox{et}\quad
\lambda_{k+1}=\lambda_k^{\text{PQ}}.
</math></center>

==== Définition de l'algorithme OQS ====

On peut à présent définir l'algorithme OQS.

{{Théorème|Algorithme OQS|Une itération passe d'un couple primal-dual <math>(x_k,\lambda_k)\in\mathbb{E}\times\R^m</math> au suivant <math>(x_{k+1},\lambda_{k+1})\in\mathbb{E}\times\R^m</math> comme suit.
# ''Résolution du PQO'' : si possible (sinon on s'arrête), trouver une solution primale duale <math>(d_k,\lambda_k^{\text{PQ}})</math> du problème quadratique osculateur<center><math>(\mbox{PQO})\quad\left\{\begin{array}{l}\inf_d\,\langle\nabla f(x_k),d\rangle +\frac{1}{2}\,\langle L_kd,d\rangle \\c_E (x_k) + c_E'(x_k)d = 0 \\c_I (x_k) + c_I'(x_k)d \leqslant 0.\end{array} \right.</math></center>
# ''Nouvel itéré'' : prendre comme nouvel itéré
<center><math>
x_{k+1}=x_k+d_k
\quad\mbox{et}\quad
\lambda_{k+1}=\lambda_k^{\text{PQ}}.
</math></center>}}

Quelques remarques s'imposent.
* D'abord, il se peut que le problème quadratique osculateur n'ait pas de solution. Comme signalé, dans sa version simplifiée présentée ci-dessus, l'algorithme n'a alors pas d'autre choix que de s'arrêter. Comme il s'agit d'un problème quadratique, cela ne peut arriver que pour deux raisons :
** le PQO n'est pas réalisable (ses contraintes linéarisées sont incompatibles, sa valeur optimale vaut alors <math>+\infty</math>) ;
** le PQO est réalisable mais n'est pas borné (sa valeur optimale vaut alors <math>-\infty</math>).
: Ces deux situations peuvent très bien se produire même si <math>(x_k,\lambda_k)</math> est proche d'une solution primale-duale <math>(x_*,\lambda_*)</math> de <math>(P_{EI})</math>. Nous verrons ci-dessous des conditions pour qu'elles n'aient pas lieu. Il existe des techniques pour faire face aux deux situations signalées ci-dessus.
* Clairement, le PQO représente la partie la plus coûteuse de l'algorithme. Le temps de calcul est nettement plus élevé que celui de la résolution d'un [[système linéaire]], requis par l'[[Méthode de Newton|algorithme de Newton]]. Ceci est surtout vrai lorsque les itérés sont éloignés d'une solution, car lorsqu'ils sont proches d'une solution primale-duale satisfaisant la complémentarité stricte, le problème quadratique osculateur se ramène à un problème quadratique avec seulement des contraintes d'égalité, dont l'équation d'optimalité est un système linéaire.
: Mais en toute généralité, le PQO est [[NP-ardu]]. Il devient résoluble en temps polynomial si <math>L_k</math> est semi-définie positive (le PQO est convexe dans ce cas). C'est une des raisons pour lesquelles on préfère parfois approcher <math>L_k</math> par une [[matrice définie positive]] (version quasi-Newtonienne de l'algorithme).
* Rien n'est fait dans cet algorithme pour forcer sa convergence si le premier itéré est éloigné d'une solution (on parle de ''globalisation'' de l'algorithme quand des moyens sont mis en œuvre pour obtenir cette propriété). Comme pour l'[[algorithme de Newton]], l'algorithme OQS ne convergera que si le premier itéré est pris suffisamment proche d'une solution et que certaines conditions sont remplies : ''lissité'' des fonctions <math>f</math> et <math>c</math> et ''régularité'' de la solution cherchée <math>(x_*,\lambda_*)</math>.

== Convergence locale ==

Le résultat suivant est dû à Bonnans (1994<ref>Voir Bonnans (1994).</ref>). On l'obtient en appliquant le résultat de convergence locale de l'[[algorithme de Josephy-Newton]].

{{Théorème|Convergence locale de l'algorithme OQS|Si 
* <math>f</math> et <math>c</math> sont de classe <math>C^{2,1}</math> dans un voisinage d'un minimum local <math>x_*</math> de <math>(P_{EI})</math>,
* il existe un ''unique'' multiplicateur optimal <math>\lambda_*\in\R^m</math> associé à <math>x_*</math>,
* les conditions suffisantes d'optimalité du second ordre on lieu,
alors il existe un voisinage <math>V</math> de <math>(x_*,\lambda_*)</math> tel que si le premier itéré <math>(x_1,\lambda_1)\in V</math>,
* l'algorithme OQS est bien défini (il ''peut'' calculer une suite d'itérés <math>\{(x_k,\lambda_k)\}</math>),
* la convergence la suite <math>\{(x_k,\lambda_k)\}</math> vers <math>(x_*,\lambda_*)</math> est quadratique.}}

La convergence locale est donc garantie si <math>f</math> et <math>c</math> sont suffisamment lisses et si une condition de régularité du point limite <math>(x_*,\lambda_*)</math> est vérifiée, exprimée par le couple : unicité du multiplicateur et conditions suffisantes d'optimalité du second ordre.

== Globalisation ==

L'algorithme OQS est une méthode locale, conçue, [[#L'algorithme OQS|on l'a dit]], en linéarisant les conditions d'optimalité du premier ordre (KKT) du problème <math>(P_{EI})</math>, aux propriétés de [[#Convergence locale|convergence locale]] remarquables. Lorsque le premier itéré n'est pas dans le voisinage d'une solution assurant la convergence de l'algorithme, celui-ci a tendance à générer des itérés au comportement erratique, qui ne convergent pas. '''Globaliser l'algorithme''' signifie donner une technique améliorant sa convergence lorsque le premier itéré n'est pas proche d'une solution (cela n'a donc rien à voir avec la recherche d'un minimum ''global''). Il n'y a pas de méthode algorithmique permettant de trouver à [[coup sûr]] une solution d'un système d'équations non linéaires de la forme <math>F(x)=0</math>, quelle que soit la fonction <math>F</math> (opérant sur <math>\R^m</math>par exemple). Il n'y a donc pas non plus de méthode permettant de trouver à coup sûr une solution de <math>(P_{EI})</math> car en l'appliquant au problème <math>{\min}_x\,\{0: F(x)=0\}</math> on serait alors assuré de trouver une solution du système non linéaire <math>F(x)=0</math>. Les techniques de globalisation de l'algorithme OQS ont donc la tâche plus modeste d'améliorer sa convergence lorsque le premier itéré est éloigné d'une solution de <math>(P_{EI})</math>.

== Annexes ==

=== Note ===

{{Références|colonnes=2}}

=== Bibliographie ===

* {{en}} J.F. Bonnans (1994). Local analysis of Newton-type methods for variational inequalities and nonlinear programming. ''Applied Mathematics and Optimization'', 29, 161–186.
* {{en}} J. F. Bonnans, J. Ch. Gilbert, C. Lemaréchal, C. Sagastizábal (2006), ''Numerical Optimization - Theoretical and Numerical Aspects'' {{détail des éditions|Référence:Optimisation (Bonnans, Gilbert, Lemaréchal, Sagastizábal, 2006)}}.
* {{en}} A.F. Izmailov, M.V. Solodov (2014). ''Newton-Type Methods for Optimization and Variational Problems'', Springer Series in Operations Research and Financial Engineering, Springer.
* {{en}} J. Nocedal, S. J. Wright (2006), [http://www.ece.northwestern.edu/~nocedal/book/num-opt.html Numerical Optimization], Springer. {{ISBN|0-387-30303-0}}.

{{Palette|Méthodes de résolution|Analyse Numérique|Optimisation}}
{{Portail|analyse}}

[[Catégorie:Algorithme d'optimisation|Optimisation quadratique successive]]