Algorithme des directions alternées
# 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.

* Minimisation en $x$ : $x_{k+1}\in \operatorname {arg\,min} _{x\in \mathbb {R} ^{n}}\,\ell _{r_{k}}(x,y_{k},\lambda _{k})$.
* Minimisation en $y$ : $y_{k+1}\in \operatorname {arg\,min} _{y\in \mathbb {R} ^{m}}\,\ell _{r_{k}}(x_{k+1},y,\lambda _{k})$.
* Nouvelle variable duale : $\lambda _{k+1}:=\lambda _{k}+r_{k}\,(Ax_{k+1}+By_{k+1}-c)$.
* Test d'arrêt : $Ax_{k+1}+By_{k+1}\simeq c$.
* 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.

