Algorithme proximal (optimisation)

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 fonction n'est pas quadratique, chaque itération requiert la minimisation d'une fonction non linéaire fortement convexe. L'algorithme peut être vu comme une méthode de 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é). Cette lecture permet alors d'en établir des propriétés de convergence, déduites de celles de l'algorithme proximal.

Sommaire

Le problème

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 f:\mathbb{H}\to\R\cup\{+\infty\} une fonction convexe semi-continue inférieurement propre. On s'intéresse au problème de trouver un minimum de f, c'est-à-dire un point x\in\mathbb{H} tel que

\forall\,x'\in\mathbb{H},\qquad f(x)\leqslant f(x').

Le problème revient à trouver une solution x de l'inclusion

\partial f(x)\ni0,

où \partial f(x) est le sous-différentiel de f en 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 f, 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

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

y\in\mathbb{H}\mapsto f_{x,r}(y):=f(y)+\frac{1}{2r}\|y-x\|^2\in\R\cup\{+\infty\}

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

f_k:=f_{x_k,r_k}.

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}=\operatorname{arg\,min}_{x\in\mathbb{H}}\, f_k(x),

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

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

0\in\partial f_k(x_{k+1})\equiv\partial f(x_{k+1})+\frac{1}{r_k}(x_{k+1}-x_k),

ce qui s'écrit aussi

x_{k+1} = x_k - r_kg_{k+1},\quad\mbox{avec}\quad g_{k+1}\in\partial f(x_{k+1}).

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

Voilà un algorithme bien étrange, puisque pour minimiser f, il faut qu'à chaque itération, l'algorithme proximal minimise la fonction fk qui semble bien être aussi compliquée que f. Ce point de vue doit être relativisé au vu des remarques suivantes.

  1. La fonction fk à minimiser (à chaque itération, ne l'oublions pas) peut être plus attrayante que 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 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 f dont l'évaluation résulte de la minimisation d'une fonction (le lagrangien) et il n'est pas plus coûteux d'évaluer f que de minimiser fk, 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 \mathbb{E}=\R^n et f est séparable, c'est-à-dire si elle s'écrit comme suit

    f(x)=\sum_{j=1}^Nf_j(x_{D_j}),

    où les Dj sont de petites parties de l'ensemble des indices \{1,\ldots,n\}, il en est de même de fk. 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 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.

Convergence

Résolution approchée

Le calcul de l'itéré suivant par 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.

Critères d'arrêt de Rockafellar

Rockafellar (1976a) propose de se contenter d'un xk + 1 vérifiant

\mbox{(R1)}\qquad \operatorname{dist}\Bigl(r_k\partial f_k(x_{k+1}),0\Bigr)\leqslant\varepsilon_k,\qquad \mbox{avec}~~ \sum_{k\geqslant0}\varepsilon_k<\infty.

Ce critère requiert la connaissance complète du sous-différentiel \partial f(x_{k+1}), ce qui est rarement aisé. Cependant, si l'on connait un élément g_{k+1}\in\partial f(x_{k+1}), le critère pourra être renforcé en y remplaçant \operatorname{dist}(r_k\partial f_k(x_{k+1}),0) par \|x_{k+1}+r_kg_{k+1}-x_k\| puisque x_{k+1}+r_kg_{k+1}-x_k\in r_k\partial f_k(x_{k+1}).

On a le résultat de convergence faible suivant[2].

Convergence faible — On suppose que f est propre convexe fermée. On considère l'algorithme proximal avec le critère d'arrêt (R1) et rk uniformément positif. On note {xk} la suite générée par l'algorithme. Alors

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

f(x_k)-f(\bar{x})\leq\left(\frac{\varepsilon_k+\|x_{k+1}-x_k\|}{r_k}\right)\|x_{k+1}-\bar{x}\|\to0.

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

\mbox{(R2)}\qquad \operatorname{dist}\Bigl(r_k\partial f_k(x_{k+1}),0\Bigr)\leqslant\varepsilon_k\|x_{k+1}-x_k\|,\qquad \mbox{avec}~~ \sum_{k\geqslant 0}\varepsilon_k<\infty.

On peut faire pour ce critère, la même remarque que celle faite pour le critère (R1), concernant le calcul du sous-différentiel \partial f(x_{k+1}).

On a alors le résultat de convergence forte suivant[3]. On y impose que (\partial f)^{-1} soit localement radialement lipschitzienne de module L en zéro, ce qui signifie que

\left\{\begin{array}{l} f~\mbox{a un unique minimiseur}~\bar{x}, \\ \exists\,\delta>0:~~ s\in\partial f(x),~~ \|s\|\leqslant\delta \quad\Longrightarrow\quad \|x-\bar{x}\|\leqslant L\|s\|. \end{array}\right.

D'autres expressions de cette propriété sont données dans le résultat, en termes de f et de sa conjuguée f * .

Convergence forte — On suppose que f est propre convexe fermée, qu'elle a un unique minimiseur \bar{x} et que, pour une constante L > 0, elle vérifie l'une des propriétés équivalentes suivantes :

  • (\partial f)^{-1} est localement radialement lipschitzienne en zéro de module L,
  • pour x voisin de \bar{x}, on a f(x)\geqslant f(\bar{x})+1/(2L)\|x-\bar{x}\|^2,
  • pour s voisin de 0, on a f^*(s)\leqslant f^*(0)+\langle s,\bar{x}\rangle+(L/2)\|s\|^2.

On considère l'algorithme proximal avec le critère d'arrêt (R2) et des paramètres rk uniformément positifs. 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},\quad \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}.

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. ↑ Théorème 4 chez Rockafellar (1976a).
  3. ↑ Réunion du théorème 2 et de la proposition 7 chez Rockafellar (1976a).

Lien externe

Bibliographie

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

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • 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 …   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”