Algorithme proximal (optimisation)

Soient ${\displaystyle \mathbb {H} }$ un espace de Hilbert, dont le produit scalaire est noté ${\displaystyle \langle \cdot ,\cdot \rangle }$ et la norme associée est notée ${\displaystyle \|\cdot \|}$, et ${\displaystyle f:\mathbb {H} \to \mathbb {R} \cup \{+\infty \}}$ une fonction convexe semi-continue inférieurement propre. On s'intéresse au problème de trouver un minimum de ${\displaystyle f}$, c'est-à-dire un point ${\displaystyle x\in \mathbb {H} }$ tel que

Le problème revient à trouver une solution ${\displaystyle x}$ de l'inclusion

où ${\displaystyle \partial f(x)}$ est le sous-différentiel de ${\displaystyle f}$ en ${\displaystyle x}$, parce que cette inclusion est une condition nécessaire et suffisante d'optimalité du problème de minimisation. On montre que, sous les propriétés énoncées de ${\displaystyle f}$, ${\displaystyle x\multimap \partial f(x)}$ est un opérateur monotone maximal[1], ce qui permet de voir le problème comme un cas particulier de recherche de zéro d'opérateur monotone maximal et de voir l'algorithme proximal en optimisation comme un cas particulier de l'algorithme proximal pour la recherche de zéro de tels opérateurs.

L'algorithme est en partie fondé sur le fait que, lorsque ${\displaystyle f}$ est convexe fermée propre et ${\displaystyle r>0}$, la fonction

est fortement convexe, de module ${\displaystyle r^{-1}}$, fermée propre et a donc un minimiseur unique. Dans la description de l'algorithme ci-dessous, on note

Exprimé autrement, le calcul du nouvel itéré consiste à trouver l'unique solution ${\displaystyle x_{k+1}}$ de l'inclusion

ce qui s'écrit aussi

L'algorithme peut donc être vu comme une méthode de sous-gradient implicite (dans le sens où le sous-gradient est évalué au nouveau point ${\displaystyle x_{k+1}}$ – inconnu – et non pas en l'itéré courant ${\displaystyle x_{k}}$) avec pas ${\displaystyle r_{k}}$. On voit aussi que chaque itération requiert la résolution d'un problème d'optimisation non linéaire (à moins que ${\displaystyle f}$ ne soit quadratique).

Pour expliquer le principe contre-intuitif de l'algorithme, puisque pour minimiser ${\displaystyle f}$, il faut qu'à chaque itération, l'algorithme proximal minimise la fonction ${\displaystyle f_{k}}$ qui semble bien être aussi compliquée que ${\displaystyle f}$, on peut remarquer les points suivants.

1. La fonction ${\displaystyle f_{k}}$ à minimiser (à chaque itération, ne l'oublions pas) peut être plus attrayante que ${\displaystyle f}$, du fait de sa forte convexité. Pour certains algorithmes, cette propriété est une aubaine, permettant d'accélérer leur convergence et de mieux la contrôler. Cette fonction a aussi un minimum unique, ce qui n'est pas nécessairement le cas de ${\displaystyle f}$.
2. Certains algorithmes de dualité peuvent être interprétés comme des algorithmes proximaux. Ces algorithmes de dualité s'appliquent en fait à des fonctions ${\displaystyle f}$ dont l'évaluation résulte de la minimisation d'une fonction (le lagrangien) et il n'est pas plus coûteux d'évaluer ${\displaystyle f}$ que de minimiser ${\displaystyle f_{k}}$, qui revient à minimiser une autre fonction (le lagrangien augmenté). Ces algorithmes de dualité ont donc tout leur sens. Leur interprétation en termes d'algorithme proximal permet alors d'en obtenir des propriétés difficiles à mettre en évidence autrement.
3. Observons que si ${\displaystyle \mathbb {E} =\mathbb {R} ^{n}}$ et ${\displaystyle f}$ est séparable, c'est-à-dire si elle s'écrit comme suit
   ${\displaystyle f(x)=\sum _{j=1}^{N}f_{j}(x_{D_{j}}),}$
   
   où les ${\displaystyle D_{j}}$ sont de petites parties de l'ensemble des indices ${\displaystyle \{1,\ldots ,n\}}$, il en est de même de ${\displaystyle f_{k}}$. C'est une propriété intéressante lorsqu'on cherche à résoudre de grands problèmes par des techniques de décomposition.
4. L'algorithme proximal a un effet stabilisant. Lorsque ${\displaystyle f}$ a plusieurs minimiseurs, l'algorithme génère une suite convergeant vers l'un d'entre eux. L'algorithme proximal est parfois utilisé pour stabiliser des algorithmes qui ne convergeraient pas sans modification lorsque le problème considéré devient singulier.

Le calcul de l'itéré suivant par ${\displaystyle x_{k+1}=\operatorname {arg\,min} _{x\in \mathbb {H} }\,f_{k}(x)}$ est souvent coûteux en temps de calcul. Dès lors, l'on se contente souvent d'un calcul approché conservant toutefois les propriétés de convergence de l'algorithme idéal. On peut aussi arguer que ce calcul ne peut être réalisé exactement en arithmétique flottante. Différents critères ont donc été proposés pour déterminer ce qu'est une résolution approchée acceptable.