Algorithme proximal

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 la méthode des multiplicateurs (ou algorithme du lagrangien augmenté) — ce qui permet d'en établir des propriétés de convergence.

Sommaire

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

T(x)\ni0.

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\R\cup\{+\infty\} sur un espace de Hilbert \mathbb{H} revient à résoudre l'inclusion \partial f(x)\ni0, c'est-à-dire à trouver un zéro de son sous-différentiel \partial f, qui est un opérateur monotone maximal[1]. 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[2]. Les algorithmes proximaux en optimisation sont présentés ailleurs.

Inéquations variationnelles

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\geqslant0,\quad\forall\,x'\in K.

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

T(x) = F(x) + NK(x),

où NK(x) est le cône normal à K en x (si x\notin K, NK(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[3]. 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

Pr: = (I + rT) − 1

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

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 xk + 1 à partir de xk par

x_{k+1}=P_{r_k}(x_k),

où rk > 0 est un nombre réel pouvant être modifié à chaque itération.

Exprimé autrement, le calcul de l'itéré xk + 1 consiste à trouver l'unique solution de

xk + 1 + rkT(xk + 1) = xk.

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)\ni0, on est amené à résoudre une suite de problèmes auxiliaires (non linéaires) xk + 1 + rkT(xk + 1) = xk, 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.

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 xk + 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_kT(x)-x_k),

ce critère sera vérifié si xk + 1 satisfait le critère parfois implémentable suivant

\mbox{(R1b)}\qquad \operatorname{dist}\Bigl(x_{k+1}+r_kT(x_{k+1})-x_k,0\Bigr)\leqslant\varepsilon_k,\qquad \mbox{avec}~~ \sum_{k\geqslant0}\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[5].

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 rk uniformément positifs. On note {xk} la suite générée par l'algorithme. Alors

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

Rockafellar (1976a) propose aussi un critère plus exigeant, celui dans lequel on requiert le calcul d'un xk + 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 à xk + 1 de satisfaire le critère parfois implémentable suivant

\mbox{(R2b)}\qquad \operatorname{dist}\Bigl(x_{k+1}+r_kT(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[6]. 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.

Convergence forte — On considère l'algorithme proximal avec l'un des critères d'arrêt (R2a) ou (R2b) et des paramètres rk 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 {xk} est bornée. Alors {xk} 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\to0 et \theta_k\to0, ce qui implique qu'alors la suite {xk} 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 {ε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

  1. ↑ La monotonie maximale du sous-différentiel d'une fonction convexe fermée propre est due à Minty (1964) et Moreau (1965).
  2. ↑ Voir Rockafellar (1976b).
  3. ↑ La monotonie maximale de l'opérateur servant à définir un problème d'inéquations variationnelles a été démontrée par Rockafellar (1970).
  4. ↑ Voir Minty (1962).
  5. ↑ Théorème 1 chez Rockafellar (1976a).
  6. ↑ Théorème 2 chez Rockafellar (1976a). C'est apparemment le premier résultat de convergence forte pour l'algorithme proximal.

Article connexe

Bibliographie

  • (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) 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.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme proximal de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Algorithme proximal (optimisation) — En analyse numérique et plus précisément en optimisation mathématique, l algorithme proximal (ou algorithme du point proximal) est un algorithme itératif de calcul d un minimum d une fonction convexe semi continue inférieurement propre. Si la… …   Wikipédia en Français

  • Proximal — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Le mot proximal est utilisé en anatomie humaine, pour désigner une partie du corps proche de la racine d un membre, mathématiques, et plus précisément an… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”