Algorithme proximal

Un article de Wikipédia, l'encyclopédie libre.

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[modifier | modifier le code]

Énoncé[modifier | modifier le code]

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[modifier | modifier le code]

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[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é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

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[3]. Les algorithmes proximaux pour la résolution d'inéquations variationnelles sont présentés ailleurs.

L'algorithme[modifier | modifier le code]

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 [4].

Algorithme proximal — On se donne un itéré initial . L'algorithme proximal définit une suite d'itérés , en calculant à partir de par

est un nombre réel pouvant être modifié à chaque itération.

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.

  1. 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.
  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[modifier | modifier le code]

Résolution approchée[modifier | modifier le code]

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[modifier | modifier le code]

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[5].

Convergence faible — On suppose que 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 uniformément positifs. On note la suite générée par l'algorithme. Alors

  1. si n'a pas de zéro, n'est pas bornée,
  2. si a un zéro, converge faiblement vers un zéro de et (convergence forte dans ).

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[6]. 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[7], soit aucun[8].

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

avec .

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

Autre critère d'arrêt[modifier | modifier le code]

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[modifier | modifier le code]

Notes[modifier | modifier le code]

  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.
  7. Voir Luque (1984)
  8. Voir Bruck et Reich (1977), Reich (1977), Spingarn (1987).

Article connexe[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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