Algorithme des directions alternées

L'algorithme des directions alternées (l'ADA ou l'algorithme des DA ; en anglais ADMM pour Alternating Direction Method of Multipliers (en)) est un algorithme de résolution de problèmes d'optimisation décomposables, qui cherche à adapter l'algorithme du lagrangien augmenté à ce contexte, alors que cet algorithme détruit cette décomposabilité. Il est typiquement utilisé pour minimiser la somme de deux fonctions (souvent convexes) dépendant de variables différentes couplées par une contrainte affine :

$\left\{{\begin{array}{l}\textstyle \inf _{(x,y)}\;f(x)+g(y)\\Ax+By=c,\end{array}}\right.$

où $f:\mathbb {R} ^{n}\to \mathbb {R} \cup \{+\infty \}$ et $g:\mathbb {R} ^{m}\to \mathbb {R} \cup \{+\infty \}$, $A\in \mathbb {R} ^{p\times n}$, $B\in \mathbb {R} ^{p\times m}$ et $c\in \mathbb {R} ^{p}$. L’algorithme suppose implicitement que minimiser $f$ ou $g$ seul est facile.

C'est un algorithme trouvant rapidement une solution avec peu de précision, mais qui demande beaucoup d'itérations pour déterminer une solution avec précision.

L'algorithme est utilisé dans des domaines très variés dans lesquels la précision de la solution importe peu : technique d'apprentissage statistique, machine à vecteurs de support, régularisation $\ell _{1}$ des problèmes de moindres-carrés, régression logistique creuse, etc.

Le problème à résoudre

On se place dans le contexte donné en introduction, à savoir celui où l'on cherche à minimiser la somme de deux fonctions dépendant de variables différentes couplées par une contrainte affine :

$(P)\qquad \left\{{\begin{array}{l}\textstyle \inf _{(x,y)}\;f(x)+g(y)\\Ax+By=c,\end{array}}\right.$

où $f:\mathbb {R} ^{n}\to \mathbb {R} \cup \{+\infty \}$ et $g:\mathbb {R} ^{m}\to \mathbb {R} \cup \{+\infty \}$, $A\in \mathbb {R} ^{p\times n}$, $B\in \mathbb {R} ^{p\times m}$ et $c\in \mathbb {R} ^{p}$.

Exemple 1. On peut utiliser l'algorithme des DA pour minimiser la somme de deux fonctions convexes $f+g:\mathbb {R} ^{n}\to \mathbb {R} \cup \{+\infty \}$ par duplication des variables :

$\left\{{\begin{array}{l}\textstyle \inf _{(x,y)}\;f(x)+g(y)\\x=y.\end{array}}\right.$

Exemple 2, qui tire parti du fait que les fonctions peuvent prendre des valeurs infinies. On cherche à minimiser une fonction $f:\mathbb {R} ^{n}\to \mathbb {R}$ sur un ensemble $X\subset \mathbb {R} ^{n}$. Comme ce problème revient à minimiser $f+{\mathcal {I}}_{X}$, où ${\mathcal {I}}_{X}$ est la fonction indicatrice de $X$, on se ramène au problème de l'exemple 1, traitant de la minimisation d'une somme de deux fonctions.

L'algorithme

L'algorithme se présente le mieux en le voyant comme une modification de l'algorithme du lagrangien augmenté, cherchant à préserver la décomposabilité supposée des fonctions $f$ et $g$. Nous commençons donc par rappeler celui-ci.

L'algorithme du lagrangien augmenté

Le lagrangien augmenté, associé au problème $(P)$ ci-dessus, est la fonction

$\ell _{r}:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} \cup \{+\infty \},$

dont la valeur en $(x,y,\lambda )\in \mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}$ s'écrit

$\ell _{r}(x,y,\lambda )=f(x)+g(y)+\lambda ^{\top }(Ax+By-c)+{\frac {r}{2}}\|Ax+By-c\|_{2}^{2},$

où $r\geqslant 0$ est le paramètre d'augmentation. Si $r=0$ on retrouve le lagrangien du problème.

Une itération de l'algorithme du lagrangien augmenté fait passer d'une estimation $\lambda _{k}\in \mathbb {R} ^{p}$ d'un multiplicateur optimal à l'estimation suivante $\lambda _{k+1}\in \mathbb {R} ^{p}$ en deux étapes :

${\begin{array}{c}\textstyle (x_{k+1},y_{k+1})\in \operatorname {arg\,min} _{(x,y)\in \mathbb {R} ^{n}\times \mathbb {R} ^{m}}\ell _{r}(x,y,\lambda _{k}),\\\lambda _{k+1}=\lambda _{k}+r_{k}(Ax_{k+1}+By_{k+1}-c).\end{array}}$

L'inconvénient de la première étape est de devoir minimiser le lagrangien augmenté simultanément en $x$ et $y$, alors que le terme de pénalisation quadratique de la contrainte couple ces variables (il n'est pas possible de faire la minimisation séparément en $x$ et en $y$). C'est à cet inconvénient que remédie l'algorithme des DA.

L'algorithme des directions alternées

Algorithme des directions alternées — Une itération passe d'un quadruplet $(x_{k},y_{k},\lambda _{k},r_{k})\in \mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\times \mathbb {R}$ au suivant $(x_{k+1},y_{k+1},\lambda _{k+1},r_{k+1})$ comme suit.

1. Minimisation en $x$ : $x_{k+1}\in \operatorname {arg\,min} _{x\in \mathbb {R} ^{n}}\,\ell _{r_{k}}(x,y_{k},\lambda _{k})$.
2. Minimisation en $y$ : $y_{k+1}\in \operatorname {arg\,min} _{y\in \mathbb {R} ^{m}}\,\ell _{r_{k}}(x_{k+1},y,\lambda _{k})$.
3. Nouvelle variable duale : $\lambda _{k+1}:=\lambda _{k}+r_{k}\,(Ax_{k+1}+By_{k+1}-c)$.
4. Test d'arrêt : $Ax_{k+1}+By_{k+1}\simeq c$.
5. Nouveau paramètre d'augmentation : $r_{k+1}$.

Remarques.

• C'est la minimisation séparée en $x$ et $y$ qui permet de faire de la décomposition lorsque $f$ et $g$ sont séparables.
• Si l'on minimisait d'abord en $y$ puis en $x$ avant de mettre à jour $\lambda$, on obtiendrait des itérés différents.
• L'algorithme des DA est un algorithme lent, si l'on veut une solution précise (il vaut mieux alors utiliser des algorithmes tenant compte des dérivées secondes ou d'une approximation de celles-ci), mais rapide si l'on se contente d'une précision modérée.
• On attribue généralement cet algorithme à Glowinski et Marocco (1975), ainsi qu'à Gabay et Mercier (1976).

Interprétations

L'algorithme peut se voir comme une méthode de Gauss-Seidel par bloc, tronquée à une seule passe, pour minimiser le lagrangien augmenté, avant de modifier le multiplicateur. Cependant aucun résultat de convergence n'utilise cette interprétation, si bien qu'elle est contestée par certains.

L'algorithme peut être vu comme réalisant une composition d'opérateurs contractants.

L'algorithme peut aussi être vu comme un cas particulier de l'algorithme de Douglas-Rachford, qui est lui-même un cas particulier de l'algorithme proximal.

Annexes

Références

• (en) J. Eckstein (1989). Splitting Methods for Monotone Operators with Applications to Parallel Optimization. Thèse de doctorat, Massachusetts Institute of Technology.
• (en) J. Eckstein (2012). Augmented Lagrangian and alternating direction methods for convex optimization: a tutorial and some illustrative computational results. RRR 32-2012, Department of Management Science and Information Systems (MSIS) and RUTCOR, Rutgers University, 640 Bartholomew Road, Piscataway, NJ 08854-8003.
• (en) J. Eckstein, D. P. Bertsekas (1992). On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55, 293–318.
• (en) J. Eckstein, M. C. Ferris (1998). Operator-splitting methods for monotone affine variational inequalities, with a parallel application to optimal control. INFORMS Journal on Computing, 10, 218–235.
• M. Fortin, R. Glowinski (1982). Méthodes de Lagrangien Augmenté – Applications à la Résolution Numérique de Problèmes aux Limites. Méthodes Mathématiques de l’Informatique 9. Dunod, Paris.
• (en) D. Gabay (1983). Applications of the method of multipliers to variational inequalities. In M. Fortin, R. Glowinski, éditeurs, Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, pages 299–331. North-Holland, Ams- terdam.
• (en) D. Gabay, B. Mercier (1976). A dual algorithm for the solution of nonlinear variational problems via finite-element approximations. Computers and Mathematics with Applications, 2, 17–40.
• R. Glowinski, A. Marocco (1975). Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation dualité, d’une classe de problèmes de Dirichlet non linéaires. Revue Française d’Automatique, Informatique et Recherche Opérationnelle, R-9, 41–76.
• (en) J. Lawrence, J. E. Spingarn (1987). On fixed points of nonexpansive piecewise isometric mappings. Proc. London Math. Soc., 55, 605–624.
• (en) P.-L. Lions, B. Mercier (1979). Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis, 16, 964–979.