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 newtonien appliqué aux 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 calcul différentiel (on linéarise des fonctions) et les 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

$(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.$

où le critère $f:\mathbb {E} \to \mathbb {R}$ est défini sur un espace euclidien $\mathbb {E}$, ainsi que les fonctions $c_{i}:\mathbb {E} \to \mathbb {R}$, que l'on appelle contraintes. Le produit scalaire de l'espace euclidien $\mathbb {E}$ est noté $\langle \cdot ,\cdot \rangle$. Les contraintes sont en nombre fini, repérées par des ensembles finis d'indices $E$ et $I$, dont le cardinal est noté

$m_{E}:=|E|\qquad {\mbox{et}}\qquad m_{I}:=|I|$.

Le nombre total de contraintes est noté $m:=m_{E}+m_{I}$. Les inégalités vectorielles, comme $c_{I}(x)\leqslant 0$, doivent se comprendre composante par composante : $c_{i}(x)\leqslant 0$ pour tout $i\in I$.

Il est commode de supposer que les ensembles d'indices $E$ et $I$ forment une partition de l'ensemble des $m$ premiers entiers $[1:m]$ :

$E\cup I=[1:m]\qquad {\mbox{et}}\qquad E\cap I=\varnothing .$

Si $v\in \mathbb {R} ^{m}$, on note $v_{E}$ le vecteur de $\mathbb {R} ^{m_{E}}$ formé des composantes $v_{i}$ de $v$ avec $i\in E$. De même pour $v_{I}$. On peut alors rassembler les fonctions réelles $c_{i}$ en une seule fonction $c:\mathbb {E} \to \mathbb {R} ^{m}$, dont les composantes $c_{E}$ et $c_{I}$ sont utilisées pour définir les contraintes d'égalité et d'inégalité. Pour un vecteur $v\in \mathbb {R} ^{m}$, on définit $v^{\#}\in \mathbb {R} ^{m}$ par

$[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.$

On rappelle que le lagrangien du problème $(P_{EI})$ est la fonction $\ell :\mathbb {E} \times \mathbb {R} ^{m}\to \mathbb {R}$ définie en $(x,\lambda )\in \mathbb {E} \times \mathbb {R} ^{m}$ par

$\ell (x,\lambda ):=f(x)+\lambda ^{\!\top \!}c(x)=f(x)+\sum _{i=1}^{m}\lambda _{i}c_{i}(x).$

Le vecteur $\lambda$ 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 $(P_{EI})$ procédant par linéarisation des conditions d'optimalité du premier ordre de ce problème, celles de 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 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 $(x_{k},\lambda _{k})\in \mathbb {E} \times \mathbb {R} ^{m}$, où $x_{k}$ approche une solution $x_{*}$ de $(P_{EI})$ (dite solution primale car appartenant à $\mathbb {E}$) et $\lambda _{k}$ approche un multiplicateur optimal $\lambda _{*}\in \mathbb {R} ^{m}$ de $(P_{EI})$ (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é du premier ordre ou conditions de Karush, Kuhn et Tucker (KKT) de $(P_{EI})$. C'est aussi en adoptant ce point de vue que l'on obtient les meilleurs résultats de convergence.

Les conditions d'optimalité de KKT s'écrivent en une solution $x_{*}\in \mathbb {E}$ : il existe un multiplicateur optimal $\lambda _{*}\in \mathbb {R} ^{m}$ tel que

$({\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.$

Dans ce système, $c'(x_{*})^{*}:\mathbb {R} ^{m}\to \mathbb {E}$ est l'opérateur adjoint de l'opérateur linéaire dérivée $c'(x_{*}):\mathbb {E} \to \mathbb {R} ^{m}$ et la dernière identité signifie que $(\lambda _{*})_{I}\geqslant 0$ (positivité des multiplicateurs optimaux associés aux contraintes d'inégalité), que $c_{I}(x_{*})\leqslant 0$ (satisfaction des contraintes d'inégalité) et que $(\lambda _{*})_{I}^{\mathsf {T}}c_{I}(x_{*})=0$ (complémentarité). Ce système d'optimalité en $z_{*}:=(x_{*},\lambda _{*})$ s'écrit aussi comme l'inclusion fonctionnelle

$F(z_{*})+\operatorname {N} _{K}(z_{*})\ni 0$

dans laquelle la fonction $F:\mathbb {E} \times \mathbb {R} ^{m}\to \mathbb {E} \times \mathbb {R} ^{m}$ est définie en $z=(x,\lambda )$ par

$F(z)={\begin{pmatrix}\nabla _{x}\ell (x,\lambda )\\-c(x)\end{pmatrix}}$

et $\operatorname {N} _{K}(z)$ est le cône normal en $z$ au cône convexe polyédrique $K:=\mathbb {E} \times (\mathbb {R} ^{m_{E}}\times \mathbb {R} _{+}^{m_{I}})$. La nature convexe conique de $K$ implique que l'inclusion fonctionnelle ci-dessus s'écrit aussi sous la forme du problème de complémentarité non linéaire suivant

$K\ni z_{*}\perp F(x_{*})\in K^{+},$

où $K^{+}$ est le cône dual de $K$. On voit alors aisément l'équivalence de ce système avec (KKT) en notant que $K^{+}:=\{0_{\mathbb {E} }\}\times (\{0_{\mathbb {R} ^{m_{E}}}\}\times \mathbb {R} _{+}^{m_{I}})$.

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 $z_{k+1}:=(x_{k+1},\lambda _{k+1})$ à partir de l'itéré courant $z_{k}:=(x_{k},\lambda _{k})$ comme solution (si une telle solution existe) de l'équation linéarisée (en réalité, on ne linéarise que $F$) :

$F(z_{k})+F'(z_{k})(z-z_{k})\operatorname {N} _{K}(z)\ni 0\quad {\mbox{ou}}\quad K\ni z\perp F(z_{k})+F'(z_{k})(z-z_{k})\in K^{+}.$

Si l'on note $(d_{k},\mu _{k}):=z_{k+1}-z_{k}=(x_{k+1}-x_{k},\lambda _{k+1}-\lambda _{k})$ on obtient le système de complémentarité linéaire suivant à résoudre

$\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.$

où $L_{k}$ est la hessienne $\nabla _{xx}^{2}\ell (x_{k},\lambda _{k})$ du lagrangien $\ell$ par rapport à $x$ (voir ci-dessus).

La résolution de ce système en $(d_{k},\lambda _{k+1})$ ($\lambda _{k}$ est «caché» dans $L_{k}$) 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 $d\in \mathbb {R} ^{n}$ suivant

$({\mbox{PQO}})\quad \left\{{\begin{array}{l}\inf _{d}\,\langle \nabla f(x_{k}),d\rangle +{\frac {1}{2}}\,\langle L_{k}d,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.$

Celui-ci porte le nom de problème quadratique osculateur du problème $(P_{EI})$. Si $(d_{k},\lambda _{k}^{\text{PQ}})\in \mathbb {E} \times \mathbb {R} ^{m}$ est une solution primale-duale, le nouvel itéré sera

$x_{k+1}=x_{k}+d_{k}\quad {\mbox{et}}\quad \lambda _{k+1}=\lambda _{k}^{\text{PQ}}.$

Définition de l'algorithme OQS

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

Algorithme OQS — Une itération passe d'un couple primal-dual $(x_{k},\lambda _{k})\in \mathbb {E} \times \mathbb {R} ^{m}$ au suivant $(x_{k+1},\lambda _{k+1})\in \mathbb {E} \times \mathbb {R} ^{m}$ comme suit.

1. Résolution du PQO : si possible (sinon on s'arrête), trouver une solution primale duale $(d_{k},\lambda _{k}^{\text{PQ}})$ du problème quadratique osculateur$({\mbox{PQO}})\quad \left\{{\begin{array}{l}\inf _{d}\,\langle \nabla f(x_{k}),d\rangle +{\frac {1}{2}}\,\langle L_{k}d,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.$
2. Nouvel itéré : prendre comme nouvel itéré

$x_{k+1}=x_{k}+d_{k}\quad {\mbox{et}}\quad \lambda _{k+1}=\lambda _{k}^{\text{PQ}}.$

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 $+\infty$) ;
  • le PQO est réalisable mais n'est pas borné (sa valeur optimale vaut alors $-\infty$).

Ces deux situations peuvent très bien se produire même si $(x_{k},\lambda _{k})$ est proche d'une solution primale-duale $(x_{*},\lambda _{*})$ de $(P_{EI})$. 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'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 $L_{k}$ 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 $L_{k}$ 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 $f$ et $c$ et régularité de la solution cherchée $(x_{*},\lambda _{*})$.

Convergence locale

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

Convergence locale de l'algorithme OQS — Si

• $f$ et $c$ sont de classe $C^{2,1}$ dans un voisinage d'un minimum local $x_{*}$ de $(P_{EI})$,
• il existe un unique multiplicateur optimal $\lambda _{*}\in \mathbb {R} ^{m}$ associé à $x_{*}$,
• les conditions suffisantes d'optimalité du second ordre on lieu,

alors il existe un voisinage $V$ de $(x_{*},\lambda _{*})$ tel que si le premier itéré $(x_{1},\lambda _{1})\in V$,

• l'algorithme OQS est bien défini (il peut calculer une suite d'itérés $\{(x_{k},\lambda _{k})\}$),
• la convergence la suite $\{(x_{k},\lambda _{k})\}$ vers $(x_{*},\lambda _{*})$ est quadratique.

La convergence locale est donc garantie si $f$ et $c$ sont suffisamment lisses et si une condition de régularité du point limite $(x_{*},\lambda _{*})$ 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, on l'a dit, en linéarisant les conditions d'optimalité du premier ordre (KKT) du problème $(P_{EI})$, aux propriétés de 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 $F(x)=0$, quelle que soit la fonction $F$ (opérant sur $\mathbb {R} ^{m}$par exemple). Il n'y a donc pas non plus de méthode permettant de trouver à coup sûr une solution de $(P_{EI})$ car en l'appliquant au problème ${\min }_{x}\,\{0:F(x)=0\}$ on serait alors assuré de trouver une solution du système non linéaire $F(x)=0$. 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 $(P_{EI})$.

Annexes

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].
• (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), Numerical Optimization, Springer. (ISBN 0-387-30303-0).