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  un espace de Hilbert, dont le produit scalaire est noté  et la norme associée est notée , et  un opérateur monotone maximal (le signe  signale qu'il s'agit d'une multifonction). On s'intéresse au problème de trouver un zéro de , c'est-à-dire un point  tel que l'ensemble  contienne zéro :

Lorsque  est univoque, le problème devient celui de trouver une solution  de l'équation .

Exemples 

Optimisation

Le problème d'optimisation qui consiste à minimiser une fonction convexe fermée propre  sur un espace de Hilbert  revient à résoudre l'inclusion , c'est-à-dire à trouver un zéro de son sous-différentiel , 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  un espace de Hilbert dont le produit scalaire est noté ,  un convexe fermé non vide de  et  un opérateur univoque monotone (non nécessairement maximal) hémi-continu contenant  dans son domaine. On considère le problème qui consiste à trouver un point  vérifiant

Ce problème s'écrit sous la forme  en utilisant l'opérateur  suivant

où  est le cône normal à  en  (si ,  est vide et donc aussi ). On montre que, sous les hypothèses énoncées sur  et ,  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  est monotone maximal et , l'opérateur

est non expansif (donc univoque) et de domaine .

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

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

On peut s'interroger sur la pertinence de l'algorithme proximal. En effet, pour résoudre le problème original (non linéaire) , on est amené à résoudre une suite de problèmes auxiliaires (non linéaires) , 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.
 L'univocité et le domaine étendu de l'opérateur , propriétés non nécessairement partagées par , rendent souvent les problèmes auxiliaires plus aisés à résoudre que le problème original.
 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  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  vérifiant

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

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

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

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  vérifiant

Ce critère n'est pas non plus implémentable puisqu'il requiert le calcul de  mais, par l'estimation de  donnée ci-dessus, il est satisfait si l'on requiert à  de satisfaire le critère parfois implémentable suivant

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

On a alors le résultat de convergence forte suivant. On y impose que  soit localement radialement lipschitzienne de module  en zéro, ce qui signifie que

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

On note que si , alors  et , ce qui implique qu'alors la suite  converge superlinéairement vers .

Autre critère d'arrêt 

Les critères d'arrêt de Rockafellar ont l'inconvénient de dépendre d'une suite  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 

  R.E. Bruck, S. Reich (1977), Nonexpansive projections and resolvents of accretive operators in Banach spaces, Houston Journal of Mathematics, 3, 459–470.
  G.J. Minty (1962). Monotone (nonlinear) operators in Hilbert space. Duke Mathematical Journal, 29, 341-346.
  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.
  S. Reich (1977). On infinite products of resolvents. Rend. Classe Sci. Fis. Mat. e Nat. Accad. Naz. Lincei Ser. VIII, LXIII, Fasc. 5.
  R.T. Rockafellar (1970). On the maximality of sums of nonlinear monotone operators. Translations of the American Mathematical Society, 149, 75-88.
  R.T. Rockafellar (1976a). Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization, 14, 877–898.
  R.T. Rockafellar (1976b). Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of Operations Research, 1, 97-116.
  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.
  J.E. Spingarn (1983). Partial inverse of a monotone operator. Applied Mathematics and Optimization, 10, 247–265.

Analyse numérique