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 modifier

Le problème à résoudre modifier

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   est défini sur un espace euclidien  , ainsi que les fonctions  , que l'on appelle contraintes. Le produit scalaire de l'espace euclidien   est noté  . Les contraintes sont en nombre fini, repérées par des ensembles finis d'indices   et  , dont le cardinal est noté

 .

Le nombre total de contraintes est noté  . Les inégalités vectorielles, comme  , doivent se comprendre composante par composante :   pour tout  .

Il est commode de supposer que les ensembles d'indices   et   forment une partition de l'ensemble des   premiers entiers   :

 

Si  , on note   le vecteur de   formé des composantes   de   avec  . De même pour  . On peut alors rassembler les fonctions réelles   en une seule fonction  , dont les composantes   et   sont utilisées pour définir les contraintes d'égalité et d'inégalité. Pour un vecteur  , on définit   par

 

On rappelle que le lagrangien du problème   est la fonction   définie en   par

 

Le vecteur   porte le nom de multiplicateur (de Karush, Kuhn et Tucker ou de Lagrange) ou variable duale.

L'algorithme OQS modifier

L'algorithme OQS est une méthode primale-duale de résolution de   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  , où   approche une solution   de   (dite solution primale car appartenant à  ) et   approche un multiplicateur optimal   de   (aussi appelé solution duale).

Conception de l'algorithme OQS modifier

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  . 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   : il existe un multiplicateur optimal   tel que

 

Dans ce système,   est l'opérateur adjoint de l'opérateur linéaire dérivée   et la dernière identité signifie que   (positivité des multiplicateurs optimaux associés aux contraintes d'inégalité), que   (satisfaction des contraintes d'inégalité) et que   (complémentarité). Ce système d'optimalité en   s'écrit aussi comme l'inclusion fonctionnelle

 

dans laquelle la fonction   est définie en   par

 

et   est le cône normal en   au cône convexe polyédrique  . La nature convexe conique de   implique que l'inclusion fonctionnelle ci-dessus s'écrit aussi sous la forme du problème de complémentarité non linéaire suivant

 

  est le cône dual de  . On voit alors aisément l'équivalence de ce système avec (KKT) en notant que  .

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   à partir de l'itéré courant   comme solution (si une telle solution existe) de l'équation linéarisée (en réalité, on ne linéarise que  ) :

 

Si l'on note   on obtient le système de complémentarité linéaire suivant à résoudre

 

  est la hessienne   du lagrangien   par rapport à   (voir ci-dessus).

La résolution de ce système en   (  est «caché» dans  ) 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   suivant

 

Celui-ci porte le nom de problème quadratique osculateur du problème  . Si   est une solution primale-duale, le nouvel itéré sera

 

Définition de l'algorithme OQS modifier

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

Algorithme OQS — Une itération passe d'un couple primal-dual   au suivant   comme suit.

  1. Résolution du PQO : si possible (sinon on s'arrête), trouver une solution primale duale   du problème quadratique osculateur
     
  2. Nouvel itéré : prendre comme nouvel itéré
 

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  ) ;
    • le PQO est réalisable mais n'est pas borné (sa valeur optimale vaut alors  ).
Ces deux situations peuvent très bien se produire même si   est proche d'une solution primale-duale   de  . 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   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   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   et   et régularité de la solution cherchée  .

Convergence locale modifier

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

Convergence locale de l'algorithme OQS — Si

  •   et   sont de classe   dans un voisinage d'un minimum local   de  ,
  • il existe un unique multiplicateur optimal   associé à  ,
  • les conditions suffisantes d'optimalité du second ordre on lieu,

alors il existe un voisinage   de   tel que si le premier itéré  ,

  • l'algorithme OQS est bien défini (il peut calculer une suite d'itérés  ),
  • la convergence la suite   vers   est quadratique.

La convergence locale est donc garantie si   et   sont suffisamment lisses et si une condition de régularité du point limite   est vérifiée, exprimée par le couple : unicité du multiplicateur et conditions suffisantes d'optimalité du second ordre.

Globalisation modifier

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  , 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  , quelle que soit la fonction   (opérant sur  par exemple). Il n'y a donc pas non plus de méthode permettant de trouver à coup sûr une solution de   car en l'appliquant au problème   on serait alors assuré de trouver une solution du système non linéaire  . 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  .

Annexes modifier

Note modifier

  1. Voir Bonnans (1994).

Bibliographie modifier

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