Algorithme du lagrangien augmenté

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

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

sous conditions

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

où ${\displaystyle {\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é :

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

${\displaystyle \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 ${\displaystyle \mu _{k}}$, la variable ${\displaystyle \lambda }$ est également mise à jour selon la règle

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

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

La variable ${\displaystyle \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 ${\displaystyle \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, ${\displaystyle \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é .

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

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

Ceci est équivalent au problème contraint

${\displaystyle \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[5]. Il existe plusieurs progiciels modernes qui résolvent la poursuite de base et se variantes et utilisent l'ADA ; ces packages incluent YALL1 [6] (2009), SpaRSA [7] (2009) et SALSA [8] (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 [9] (2015), parADMM [10] (2016).

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

${\displaystyle {\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ù ${\displaystyle \eta _{k+1}}$ est une taille de pas temporel variable[11].

La méthode des directions alternées est une méthode populaire pour l'optimisation en ligne et distribuée à grande échelle[12], et est utilisée dans de nombreuses applications [13] - [14]. 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.

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

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

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

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