Algorithme proximal

En analyse numérique, l'algorithme proximal (ou algorithme du point proximal) est un algorithme itératif de calcul d'un zéro d'un opérateur monotone maximal. Si cet opérateur est non linéaire, chaque itération requiert la résolution d'un problème non linéaire.

Lorsqu'on l'applique à l'optimisation convexe, l'algorithme peut être vu comme une méthode de sous-gradient implicite.

Certains algorithmes peuvent être interprétés comme des algorithmes proximaux — il en est ainsi de l'algorithme du lagrangien augmenté (ou méthode des multiplicateurs) — ce qui permet d'en établir des propriétés de convergence.

Le problème

Énoncé

Soient $\mathbb {H}$ un espace de Hilbert, dont le produit scalaire est noté $\langle \cdot ,\cdot \rangle$ et la norme associée est notée $\|\cdot \|$, et $T:\mathbb {H} \multimap \mathbb {H}$ un opérateur monotone maximal (le signe $\multimap$ signale qu'il s'agit d'une multifonction). On s'intéresse au problème de trouver un zéro de $T$, c'est-à-dire un point $x\in \mathbb {H}$ tel que l'ensemble $T(x)$ contienne zéro :

$T(x)\ni 0.$

Lorsque $T$ est univoque, le problème devient celui de trouver une solution $x$ de l'équation $T(x)=0$.

Exemples

Optimisation

Le problème d'optimisation qui consiste à minimiser une fonction convexe fermée propre $f:\mathbb {H} \to \mathbb {R} \cup \{+\infty \}$ sur un espace de Hilbert $\mathbb {H}$ revient à résoudre l'inclusion $\partial f(x)\ni 0$, c'est-à-dire à trouver un zéro de son sous-différentiel $\partial f$, qui est un opérateur monotone maximal. Cette observation est à la base de l'algorithme proximal primal en optimisation. On peut aussi introduire un algorithme proximal dual en utilisant le sous-différentiel concave de la fonction duale et un algorithme proximal primal-dual en utilisant le sous-différentiel convexe-concave du lagrangien. Les algorithmes proximaux en optimisation sont présentés ailleurs.

Inéquation variationnelle

Soient $\mathbb {H}$ un espace de Hilbert dont le produit scalaire est noté $\langle \cdot ,\cdot \rangle$, $K$ un convexe fermé non vide de $\mathbb {H}$ et $F:K\to \mathbb {H}$ un opérateur univoque monotone (non nécessairement maximal) hémi-continu contenant $K$ dans son domaine. On considère le problème qui consiste à trouver un point $x\in \mathbb {H}$ vérifiant

$x\in K\qquad {\mbox{et}}\qquad \langle F(x),x'-x\rangle \geqslant 0,\quad \forall \,x'\in K.$

Ce problème s'écrit sous la forme $T(x)\ni 0$ en utilisant l'opérateur $T:\mathbb {H} \multimap \mathbb {H}$ suivant

$T(x)=F(x)+N_{K}(x),$

où $N_{K}(x)$ est le cône normal à $K$ en $x$ (si $x\notin K$, $N_{K}(x)$ est vide et donc aussi $T(x)$). On montre que, sous les hypothèses énoncées sur $K$ et $F$, $T$ est monotone maximal. Les algorithmes proximaux pour la résolution d'inéquations variationnelles sont présentés ailleurs.

L'algorithme

L'algorithme est en partie fondé sur le fait que, lorsque $T$ est monotone maximal et $r>0$, l'opérateur

$P_{r}:=(I+rT)^{-1}$

est non expansif (donc univoque) et de domaine $\mathbb {H}$.

Algorithme proximal — On se donne un itéré initial $x_{0}\in \mathbb {H}$. L'algorithme proximal définit une suite d'itérés $x_{1},x_{2},\ldots \in \mathbb {H}$, en calculant $x_{k+1}$ à partir de $x_{k}$ par

$x_{k+1}=P_{r_{k}}(x_{k}),$

où $r_{k}>0$ est un nombre réel pouvant être modifié à chaque itération.

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

$x_{k+1}+r_{k}T(x_{k+1})=x_{k}.$

En toute généralité, cette opération est non linéaire (à moins que $T$ ne soit linéaire). Cette équation montre aussi que, même si $x_{0}\notin {\mathcal {D}}(T)$, les itérés suivants sont dans le domaine de $T$.

On peut s'interroger sur la pertinence de l'algorithme proximal. En effet, pour résoudre le problème original (non linéaire) $T(x)\ni 0$, on est amené à résoudre une suite de problèmes auxiliaires (non linéaires) $x_{k+1}+r_{k}T(x_{k+1})=x_{k}$, qui sont apparemment aussi difficiles à résoudre que le problème original. Cette critique, en apparence rédhibitoire, doit être relativisée à la lumière des remarques suivantes.

1. L'univocité et le domaine étendu de l'opérateur $P_{r_{k}}$, propriétés non nécessairement partagées par $T^{-1}$, rendent souvent les problèmes auxiliaires plus aisés à résoudre que le problème original.
2. Certains algorithmes (méthode des multiplicateurs, techniques de décomposition) s'écrivent naturellement sous la forme d'un algorithme proximal. Celui-ci est alors une interprétation de l'algorithme permettant d'en analyser les propriétés, en particulier la convergence.

Résolution approchée

Le calcul de l'itéré suivant par $x_{k+1}=P_{r_{k}}(x_{k})$ 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.

Critères d'arrêt de Rockafellar

Rockafellar (1976a) propose de se contenter d'un $x_{k+1}$ vérifiant

${\mbox{(R1a)}}\qquad \|x_{k+1}-P_{r_{k}}(x_{k})\|\leqslant \varepsilon _{k},\qquad {\mbox{avec}}~~\sum _{k\geqslant 0}\varepsilon _{k}<\infty .$

Ce critère n'est pas implémentable puisqu'il requiert le calcul de $P_{r_{k}}(x_{k})$, que l'on veut justement éviter (si $P_{r_{k}}(x_{k})$ est facilement calculable, autant l'utiliser). Son intérêt est donc essentiellement théorique. Cependant comme on peut montrer que pour tout $x\in \mathbb {H}$, on a

$\|x-P_{r_{k}}(x_{k})\|\leq \operatorname {dist} (0,x+r_{k}T(x)-x_{k}),$

ce critère sera vérifié si $x_{k+1}$ satisfait le critère parfois implémentable suivant

${\mbox{(R1b)}}\qquad \operatorname {dist} {\Bigl (}x_{k+1}+r_{k}T(x_{k+1})-x_{k},0{\Bigr )}\leqslant \varepsilon _{k},\qquad {\mbox{avec}}~~\sum _{k\geqslant 0}\varepsilon _{k}<\infty .$

Ce critère requiert la connaissance complète de $T(x)$, ce qui n'est pas toujours le cas (que l'on songe au cas où $T(x)$ est le sous-différentiel $\partial f(x)$ d'une fonction convexe non quadratique $f$ en $x$).

On a le résultat de convergence faible suivant.

Convergence faible — On suppose que $T$ est monotone maximal. On considère l'algorithme proximal avec l'un des critères d'arrêt (R1a) ou (R1b) et des paramètres $r_{k}$ uniformément positifs. On note $\{x_{k}\}$ la suite générée par l'algorithme. Alors

1. si $T$ n'a pas de zéro, $\{x_{k}\}$ n'est pas bornée,
2. si $T$ a un zéro, $\{x_{k}\}$ converge faiblement vers un zéro de $T$ et $(x_{k+1}-x_{k})\to 0$ (convergence forte dans $\mathbb {H}$).

Rockafellar (1976a) propose aussi un critère plus exigeant, celui dans lequel on requiert le calcul d'un $x_{k+1}$ vérifiant

${\mbox{(R2a)}}\qquad \|x_{k+1}-P_{r_{k}}(x_{k})\|\leqslant \varepsilon _{k}\|x_{k+1}-x_{k}\|,\qquad {\mbox{avec}}~~\sum _{k\geqslant 0}\varepsilon _{k}<\infty .$

Ce critère n'est pas non plus implémentable puisqu'il requiert le calcul de $P_{r_{k}}(x_{k})$ mais, par l'estimation de $\|x-P_{r_{k}}(x_{k})\|$ donnée ci-dessus, il est satisfait si l'on requiert à $x_{k+1}$ de satisfaire le critère parfois implémentable suivant

${\mbox{(R2b)}}\qquad \operatorname {dist} {\Bigl (}x_{k+1}+r_{k}T(x_{k+1})-x_{k},0{\Bigr )}\leqslant \varepsilon _{k}\|x_{k+1}-x_{k}\|,\qquad {\mbox{avec}}~~\sum _{k\geqslant 0}\varepsilon _{k}<\infty .$

Ce critère requiert la connaissance complète de $T(x)$, ce qui n'est pas toujours le cas.

On a alors le résultat de convergence forte suivant. On y impose que $T^{-1}$ soit localement radialement lipschitzienne de module $L$ en zéro, ce qui signifie que

$\left\{{\begin{array}{l}T^{-1}(0)=\{{\bar {x}}\}\qquad ({\mbox{unique solution}}~{\bar {x}})\\\exists \,\delta >0:~~x\in T^{-1}(y),~~\|y\|\leqslant \delta \quad \Longrightarrow \quad \|x-{\bar {x}}\|\leqslant L\|y\|.\end{array}}\right.$

L'hypothèse d'unicité des zéros de $T$ peut être soulevée, soit en acceptant plusieurs zéros, soit aucun.

Convergence forte — On considère l'algorithme proximal avec l'un des critères d'arrêt (R2a) ou (R2b) et des paramètres $r_{k}$ uniformément positifs. Supposons que $T$ soit monotone maximal et que $T^{-1}$ soit localement radialement lipschitzienne en zéro de module $L$ (cette dernière condition requiert que $T$ ait un unique zéro ${\bar {x}}$). On suppose que la suite générée $\{x_{k}\}$ est bornée. Alors $\{x_{k}\}$ converge fortement et linéairement vers ${\bar {x}}$ :

$\exists \,{\bar {k}},~~\forall \,k\geqslant {\bar {k}}:\qquad \|x_{k+1}-{\bar {x}}\|\leqslant \theta _{k}\|x_{k}-{\bar {x}}\|,$

où $\theta _{k}:=(\mu _{k}+\varepsilon _{k})/(1-\varepsilon _{k})\leqslant {\bar {\theta }}<1$ avec $\mu _{k}:=L/(L^{2}+r_{k}^{2})^{1/2}\leqslant {\bar {\mu }}<1$.

On note que si $r_{k}\uparrow \infty$, alors $\mu _{k}\to 0$ et $\theta _{k}\to 0$, ce qui implique qu'alors la suite $\{x_{k}\}$ converge superlinéairement vers ${\bar {x}}$.

Autre critère d'arrêt

Les critères d'arrêt de Rockafellar ont l'inconvénient de dépendre d'une suite $\{\varepsilon _{k}\}$ donnée a priori, indépendante de l'observation des itérés générés. D'autres critères n'ayant pas cet inconvénient ont été proposés, comme celui de Solodov et Svaiter (1999).

Annexes

Article connexe

• Algorithme proximal (optimisation)

Bibliographie

• (en) R.E. Bruck, S. Reich (1977), Nonexpansive projections and resolvents of accretive operators in Banach spaces, Houston Journal of Mathematics, 3, 459–470.
• (en) G.J. Minty (1962). Monotone (nonlinear) operators in Hilbert space. Duke Mathematical Journal, 29, 341-346.
• (en) G.J. Minty (1964). On the monotonicity of the gradient of a convex function. Pacific Journal of Mathematics, 14, 243–247.
• J.J. Moreau (1965). Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93, 273–299.
• (en) S. Reich (1977). On infinite products of resolvents. Rend. Classe Sci. Fis. Mat. e Nat. Accad. Naz. Lincei Ser. VIII, LXIII, Fasc. 5.
• (en) R.T. Rockafellar (1970). On the maximality of sums of nonlinear monotone operators. Translations of the American Mathematical Society, 149, 75-88.
• (en) R.T. Rockafellar (1976a). Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14, 877–898.
• (en) R.T. Rockafellar (1976b). Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of Operations Research, 1, 97-116.
• (en) M.V. Solodov, B.F. Svaiter (1999). A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Analysis, 7, 323-345.
• (en) J.E. Spingarn (1983). Partial inverse of a monotone operator. Applied Mathematics and Optimization, 10, 247–265.