Algorithme du lagrangien augmenté

Les algorithmes du lagrangien augmenté sont une certaine classe d'algorithmes pour résoudre des problèmes d'optimisation sous contraintes. Elles présentent des similitudes avec les méthodes de pénalité dans le sens où elles remplacent un problème d'optimisation sous contraintes par une série de problèmes sans contrainte et ajoutent un terme de pénalité à l'objectif ; la différence est qu'une méthode du lagrangien augmenté ajoute encore un autre terme, conçu pour agir comme un multiplicateur de Lagrange. Le Lagrangien augmenté est apparenté, mais non identique à la méthode des multiplicateurs de Lagrange.

Vu différemment, l'objectif sans contrainte est le lagrangien du problème contraint, avec un terme de pénalité supplémentaire (l'augmentation).

La méthode était à l'origine connue sous le nom de méthode des multiplicateurs et a été beaucoup étudiée dans les années 1970 et 1980 comme une bonne alternative aux méthodes de pénalité. Il a été discuté pour la première fois par Magnus Hestenes et par Michael J. D. Powell en 1969. La méthode a été étudiée par R. Tyrrell Rockafellar en relation avec la dualité de Fenchel (en), en particulier en relation avec les méthodes des points proximaux, la régularisation Moreau-Yosida et les opérateurs monotones maximaux : ces méthodes ont été utilisées en optimisation structurelle. La méthode a également été étudiée par Dimitri Bertsekas, notamment dans son livre de 1982, ainsi que des extensions impliquant des fonctions de régularisation non quadratiques, telles que la régularisation entropique, qui donne naissance à la « méthode exponentielle des multiplicateurs », une méthode qui gère les contraintes d'inégalité avec une fonction lagrangienne augmentée deux fois dérivable.

Depuis les années 1970, la programmation quadratique séquentielle (PQS) et les méthodes de points intérieurs (MPI) ont suscité une attention croissante, en partie parce qu'elles utilisent plus facilement des sous-programmes de matrice creuse à partir de bibliothèques de logiciels numériques, et en partie parce que les MPI ont prouvé des résultats de complexité via la théorie de fonctions auto-concordantes (en). La méthode du Lagrangien augmenté a été rajeunie par les systèmes d'optimisation LANCELOT, ALGENCAN et AMPL, qui ont permis d'utiliser des techniques de matrices creuses sur des problèmes apparemment denses mais "partiellement séparables". La méthode est toujours utile pour certains problèmes. Vers 2007, il y a eu une résurgence des méthodes du lagrangien augmenté dans des domaines tels que le débruitage à variation totale et la détection compressée. En particulier, une variante de la méthode lagrangienne augmentée standard qui utilise des mises à jour partielles (similaire à la méthode de Gauss-Seidel pour résoudre des équations linéaires) connue sous le nom d'algorithme des directions alternées des multiplicateurs ou MDAM a attiré l'attention.

Méthode générale

On cherche à résoudre le problème sous contraintes suivant :

$\min f(\mathbf {x} )$

sous conditions

$c_{i}(\mathbf {x} )=0~\forall i\in {\mathcal {E}},$

où ${\mathcal {E}}$ désigne les indices des contraintes d'égalité. Ce problème peut être résolu comme une série de problèmes de minimisation sans contrainte. Pour référence, on liste d'abord la k^e étape de l'approche de la méthode de pénalité :

$\min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+\mu _{k}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}.$

La méthode de pénalité résout ce problème, puis à l'itération suivante, elle résout à nouveau le problème en utilisant une plus grande valeur de $\mu _{k}$ (et en utilisant l'ancienne solution comme estimation initiale ou "démarrage à chaud").

La méthode du lagrangien augmenté utilise l'objectif non contraint suivant :

$\min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+{\frac {\mu _{k}}{2}}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}+\sum _{i\in {\mathcal {E}}}~\lambda _{i}c_{i}(\mathbf {x} )$

et après chaque itération, en plus de la mise à jour des $\mu _{k}$, la variable $\lambda$ est également mise à jour selon la règle

$\lambda _{i}\leftarrow \lambda _{i}+\mu _{k}c_{i}(\mathbf {x} _{k})$

où $\mathbf {x} _{k}$ est la solution du problème sans contrainte à la k^e étape, c'est-à-dire $\mathbf {x} _{k}={\text{argmin}}\Phi _{k}(\mathbf {x} )$

La variable $\lambda$ est une estimation du multiplicateur de Lagrange, et la précision de cette estimation s'améliore à chaque étape. L' avantage majeur de la méthode est que contrairement à la méthode de pénalisation, il n'est pas nécessaire de prendre $\mu \rightarrow \infty$ afin de résoudre le problème sous contraintes initial. Au lieu de cela, en raison de la présence du terme de multiplicateur de Lagrange, $\mu$ peut rester beaucoup plus petit, évitant ainsi le mauvais conditionnement. Néanmoins, il est courant dans les implémentations pratiques de projeter les estimations des multiplicateurs dans un grand ensemble borné (sauvegardes), évitant les instabilités numériques et conduisant à une forte convergence théorique.

La méthode peut être étendue pour gérer les contraintes d'inégalité .

Méthode des directions alternées

La méthode des directions alternées est une variante du schéma du lagrangien augmenté qui utilise des mises à jour partielles pour les variables duales. Cette méthode est souvent appliquée pour résoudre des problèmes tels que

$\min _{x}f(x)+g(x).$

Ceci est équivalent au problème contraint

$\min _{x,y}f(x)+g(y),\quad {\text{avec }}\quad x=y.$

Bien que ce changement puisse sembler anodin, le problème peut maintenant être envisagé en utilisant des méthodes d'optimisation sous contraintes (en particulier, la méthode du lagrangien augmenté), et la fonction objectif est séparable en x et y. La double mise à jour nécessite de résoudre une fonction de proximité en x et y en même temps ; la technique ADA permet de résoudre approximativement ce problème en résolvant d'abord pour x avec y fixe, puis en résolvant pour y avec x fixe. Plutôt que d'itérer jusqu'à avoir convergé (comme la méthode de Jacobi), l'algorithme procède directement à la mise à jour de la variable duale, puis à la répétition du processus. Ce n'est pas équivalent à la minimisation exacte, mais on peut quand même montrer que cette méthode converge vers la bonne réponse sous certaines hypothèses. Du fait de cette approximation, l'algorithme se distingue de la méthode du lagrangien augmenté pure.

L'ADA peut être considéré comme une application de l'algorithme de Douglas-Rachford, et l'algorithme de Douglas-Rachford est à son tour une application de l'algorithme du point proximal. Il existe plusieurs progiciels modernes qui résolvent la poursuite de base et se variantes et utilisent l'ADA ; ces packages incluent YALL1 (2009), SpaRSA (2009) et SALSA (2009). Il existe également des packages qui utilisent l'ADA pour résoudre des problèmes plus généraux, dont certains peuvent exploiter plusieurs cœurs de calcul SNAPVX (2015), parADMM (2016).

Optimisation stochastique

L'optimisation stochastique considère le problème de la minimisation d'une fonction de perte avec accès à des échantillons bruités (du gradient) de la fonction. Le but est d'avoir une estimation du paramètre optimal (minimiseur) pour chaque nouvel échantillon. L'ADA est à l'origine une méthode groupée. Cependant, avec quelques modifications, elle peut également être utilisée pour l'optimisation stochastique. Étant donné que dans le cadre stochastique, on n'a accès qu'à des échantillons bruités de gradient, on utilise une approximation inexacte du lagrangien comme

${\hat {\mathcal {L}}}_{\rho ,k}=f_{1}(x_{k})+\langle \nabla f(x_{k},\zeta _{k+1}),x\rangle +g(y)-z^{T}(Ax+By-c)+{\frac {\rho }{2}}\Vert Ax+By-c\Vert ^{2}+{\frac {\Vert x-x_{k}\Vert ^{2}}{2\eta _{k+1}}},$

où $\eta _{k+1}$ est une taille de pas temporel variable.

La méthode des directions alternées est une méthode populaire pour l'optimisation en ligne et distribuée à grande échelle, et est utilisée dans de nombreuses applications . L'ADA est souvent appliqué pour résoudre des problèmes régularisés, où l'optimisation et la régularisation de la fonction peuvent être effectuées localement, puis coordonnées globalement via des contraintes. Les problèmes d'optimisation régularisés sont particulièrement pertinents dans le régime de haute dimension puisque la régularisation est un mécanisme naturel pour surmonter le caractère mal-posé et pour encourager la parcimonie dans la solution optimale, par exemple, pour une matrice creuse et de faible rang. En raison de l'efficacité de l'ADA dans la résolution de problèmes régularisés, il a un bon potentiel d'optimisation stochastique en grandes dimensions.

Approches alternatives

• Programmation quadratique séquentielle
• Programmation linéaire séquentielle
• Programmation séquentielle linéaire-quadratique

Articles connexes

• Fonction barrière (en)
• Méthode du point intérieur
• Multiplicateur de Lagrange
• Méthode de pénalité

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Augmented Lagrangian method » (voir la liste des auteurs).

Bibliographie

• Dimitri P. Bertsekas, Nonlinear Programming, Belmont, Mass, Athena Scientific, 1999 (ISBN 978-1-886529-00-7)
• E. G. Birgin et J. M. Martínez, Practical Augmented Lagrangian Methods for Constrained Optimization, Philadelphia, Society for Industrial and Applied Mathematics, 2014 (ISBN 978-1-611973-35-8, DOI 10.1137/1.9781611973365 )
• Jorge Nocedal et Stephen J. Wright, Numerical Optimization, Berlin, New York, Springer-Verlag, 2006 (ISBN 978-0-387-30303-1)