Optimisation quadratique successive

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

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

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

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

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

${\displaystyle [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 ${\displaystyle (P_{EI})}$ est la fonction ${\displaystyle \ell$ :\mathbb {E} \times \mathbb {R} ^{m}\to \mathbb {R} } définie en ${\displaystyle (x,\lambda )\in \mathbb {E} \times \mathbb {R} ^{m}}$ par

Le vecteur ${\displaystyle \lambda }$ porte le nom de multiplicateur (de Karush, Kuhn et Tucker ou de Lagrange) ou variable duale.

L'algorithme OQS est une méthode primale-duale de résolution de ${\displaystyle (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 ${\displaystyle (x_{k},\lambda _{k})\in \mathbb {E} \times \mathbb {R} ^{m}}$, où ${\displaystyle x_{k}}$ approche une solution ${\displaystyle x_{*}}$ de ${\displaystyle (P_{EI})}$ (dite solution primale car appartenant à ${\displaystyle \mathbb {E} }$) et ${\displaystyle \lambda _{k}}$ approche un multiplicateur optimal ${\displaystyle \lambda _{*}\in \mathbb {R} ^{m}}$ de ${\displaystyle (P_{EI})}$ (aussi appelé solution duale).

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 ${\displaystyle (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 ${\displaystyle x_{*}\in \mathbb {E} }$ : il existe un multiplicateur optimal ${\displaystyle \lambda _{*}\in \mathbb {R} ^{m}}$ tel que

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

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

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

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

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

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

où ${\displaystyle K^{+}}$ est le cône dual de ${\displaystyle K}$. On voit alors aisément l'équivalence de ce système avec (KKT) en notant que ${\displaystyle 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 ${\displaystyle z_{k+1}:=(x_{k+1},\lambda _{k+1})}$ à partir de l'itéré courant ${\displaystyle 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 ${\displaystyle F}$) :

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

${\displaystyle \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ù ${\displaystyle L_{k}}$ est la hessienne ${\displaystyle \nabla _{xx}^{2}\ell (x_{k},\lambda _{k})}$ du lagrangien ${\displaystyle \ell }$ par rapport à ${\displaystyle x}$ (voir ci-dessus).

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

${\displaystyle ({\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 ${\displaystyle (P_{EI})}$. Si ${\displaystyle (d_{k},\lambda _{k}^{\text{PQ}})\in \mathbb {E} \times \mathbb {R} ^{m}}$ est une solution primale-duale, le nouvel itéré sera

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

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

Algorithme OQS — Une itération passe d'un couple primal-dual ${\displaystyle (x_{k},\lambda _{k})\in \mathbb {E} \times \mathbb {R} ^{m}}$ au suivant ${\displaystyle (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 ${\displaystyle (d_{k},\lambda _{k}^{\text{PQ}})}$ du problème quadratique osculateur${\displaystyle ({\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é

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

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

• (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).