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 ${\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 T:\mathbb {H} \multimap \mathbb {H} }$ un opérateur monotone maximal (le signe ${\displaystyle \multimap }$ signale qu'il s'agit d'une multifonction). On s'intéresse au problème de trouver un zéro de ${\displaystyle T}$, c'est-à-dire un point ${\displaystyle x\in \mathbb {H} }$ tel que l'ensemble ${\displaystyle T(x)}$ contienne zéro :

${\displaystyle T(x)\ni 0.}$

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

Exemples

Optimisation

Le problème d'optimisation qui consiste à minimiser une fonction convexe fermée propre ${\displaystyle f:\mathbb {H} \to \mathbb {R} \cup \{ \infty \}}$ sur un espace de Hilbert ${\displaystyle \mathbb {H} }$ revient à résoudre l'inclusion ${\displaystyle \partial f(x)\ni 0}$, c'est-à-dire à trouver un zéro de son sous-différentiel ${\displaystyle \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 ${\displaystyle \mathbb {H} }$ un espace de Hilbert dont le produit scalaire est noté ${\displaystyle \langle \cdot ,\cdot \rangle }$, ${\displaystyle K}$ un convexe fermé non vide de ${\displaystyle \mathbb {H} }$ et ${\displaystyle F:K\to \mathbb {H} }$ un opérateur univoque monotone (non nécessairement maximal) hémi-continu contenant ${\displaystyle K}$ dans son domaine. On considère le problème qui consiste à trouver un point ${\displaystyle x\in \mathbb {H} }$ vérifiant

${\displaystyle 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 ${\displaystyle T(x)\ni 0}$ en utilisant l'opérateur ${\displaystyle T:\mathbb {H} \multimap \mathbb {H} }$ suivant

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

où ${\displaystyle N_{K}(x)}$ est le cône normal à ${\displaystyle K}$ en ${\displaystyle x}$ (si ${\displaystyle x\notin K}$, ${\displaystyle N_{K}(x)}$ est vide et donc aussi ${\displaystyle T(x)}$). On montre que, sous les hypothèses énoncées sur ${\displaystyle K}$ et ${\displaystyle F}$, ${\displaystyle 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 ${\displaystyle T}$ est monotone maximal et ${\displaystyle r>0}$, l'opérateur

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

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

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

${\displaystyle 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 ${\displaystyle T}$ ne soit linéaire). Cette équation montre aussi que, même si ${\displaystyle x_{0}\notin {\mathcal {D}}(T)}$, les itérés suivants sont dans le domaine de ${\displaystyle T}$.

On peut s'interroger sur la pertinence de l'algorithme proximal. En effet, pour résoudre le problème original (non linéaire) ${\displaystyle T(x)\ni 0}$, on est amené à résoudre une suite de problèmes auxiliaires (non linéaires) ${\displaystyle 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 ${\displaystyle P_{r_{k}}}$, propriétés non nécessairement partagées par ${\displaystyle 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.

Convergence

Résolution approchée

Le calcul de l'itéré suivant par ${\displaystyle 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 ${\displaystyle x_{k 1}}$ vérifiant

${\displaystyle {\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 ${\displaystyle P_{r_{k}}(x_{k})}$, que l'on veut justement éviter (si ${\displaystyle 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 ${\displaystyle x\in \mathbb {H} }$, on a

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

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

${\displaystyle {\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 ${\displaystyle T(x)}$, ce qui n'est pas toujours le cas (que l'on songe au cas où ${\displaystyle T(x)}$ est le sous-différentiel ${\displaystyle \partial f(x)}$ d'une fonction convexe non quadratique ${\displaystyle f}$ en ${\displaystyle x}$).

On a le résultat de convergence faible suivant.

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

${\displaystyle {\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 ${\displaystyle P_{r_{k}}(x_{k})}$ mais, par l'estimation de ${\displaystyle \|x-P_{r_{k}}(x_{k})\|}$ donnée ci-dessus, il est satisfait si l'on requiert à ${\displaystyle x_{k 1}}$ de satisfaire le critère parfois implémentable suivant

${\displaystyle {\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 ${\displaystyle T(x)}$, ce qui n'est pas toujours le cas.

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

${\displaystyle \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 ${\displaystyle T}$ peut être soulevée, soit en acceptant plusieurs zéros, soit aucun.

On note que si ${\displaystyle r_{k}\uparrow \infty }$, alors ${\displaystyle \mu _{k}\to 0}$ et ${\displaystyle \theta _{k}\to 0}$, ce qui implique qu'alors la suite ${\displaystyle \{x_{k}\}}$ converge superlinéairement vers ${\displaystyle {\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 ${\displaystyle \{\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

Notes

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.

• Portail des mathématiques