Algorithme des directions alternées

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 :

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

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

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

${\displaystyle \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 ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ sur un ensemble ${\displaystyle X\subset \mathbb {R} ^{n}}$. Comme ce problème revient à minimiser ${\displaystyle f+{\mathcal {I}}_{X}}$, où ${\displaystyle {\mathcal {I}}_{X}}$ est la fonction indicatrice de ${\displaystyle X}$, on se ramène au problème de l'exemple 1, traitant de la minimisation d'une somme de deux fonctions.

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 ${\displaystyle f}$ et ${\displaystyle g}$. Nous commençons donc par rappeler celui-ci.

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

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

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

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

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

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

${\displaystyle {\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 ${\displaystyle x}$ et ${\displaystyle 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 ${\displaystyle x}$ et en ${\displaystyle y}$). C'est à cet inconvénient que remédie l'algorithme des DA.

Remarques.

• C'est la minimisation séparée en ${\displaystyle x}$ et ${\displaystyle y}$ qui permet de faire de la décomposition lorsque ${\displaystyle f}$ et ${\displaystyle g}$ sont séparables.
• Si l'on minimisait d'abord en ${\displaystyle y}$ puis en ${\displaystyle x}$ avant de mettre à jour ${\displaystyle \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).

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^[1]. Cependant aucun résultat de convergence n'utilise cette interprétation, si bien qu'elle est contestée par certains^[2].

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

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