Méthode du gradient proximal

La mise en forme de cet article est à améliorer (juillet 2024).

La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».

Cet article est orphelin. Moins de trois articles lui sont liés (juillet 2024).

Vous pouvez aider en ajoutant des liens vers [[Méthode du gradient proximal]] dans les articles relatifs au sujet.

Les méthodes de gradient proximal sont une forme généralisée de projection utilisée pour résoudre des problèmes d'optimisation convexe non différenciables.

De nombreux problèmes intéressants peuvent être formulés sous forme de problèmes d’optimisation convexes de la forme

${\displaystyle \operatorname {min} \limits _{x\in \mathbb {R} ^{N}}\sum _{i=1}^{n}f_{i}(x)}$

où ${\displaystyle f_{i}:\mathbb {R} ^{N}\rightarrow \mathbb {R} ,\ i=1,\dots ,n}$ sont des fonctions convexes potentiellement non différenciables. Le manque de différentiabilité exclut les techniques conventionnelles d'optimisation continue comme la méthode de descente de gradient et la méthode du gradient conjugué, mais les méthodes du gradient proximal peuvent être utilisées à la place.

Les méthodes de gradient proximal commencent par une étape de séparation, dans laquelle les fonctions ${\displaystyle f_{1},...,f_{n}}$ sont utilisées individuellement afin de produire un algorithme facilement implémentable. Ils sont appelés proximaux car chaque fonction non différenciable parmi ${\displaystyle f_{1},...,f_{n}}$ intervient via son opérateur proximal . L'algorithme itératif avec seuil de retrait^[1], l'algorithme de Landweber , l'algorithme de gradient projeté, l'algorithme de projection sur ensembles convexes, la méthode de multiplicateurs de Lagrange, et la méthode de Bregman séparée sont des instances spéciales d'algorithmes proximaux^[2].

Pour la théorie des méthodes de gradient proximal du point de vue et avec des applications à la théorie de l'apprentissage statistique, voir méthodes de gradient proximal pour l'apprentissage.

L'un des algorithmes d'optimisation convexe les plus utilisés est la projection sur des ensembles convexes (POCS). Cet algorithme est utilisé pour récupérer/synthétiser un signal satisfaisant simultanément plusieurs contraintes convexes. Soit ${\displaystyle f_{i}}$ la fonction indicatrice d'un ensemble convexe fermé non vide ${\displaystyle C_{i}}$ modélisant une contrainte. On se réduit alors au problème de faisabilité convexe, qui nécessite de trouver une solution telle qu'elle se situe à l'intersection de tous les ensembles convexes. ${\displaystyle C_{i}}$. Dans la méthode POCS, chaque ensemble ${\displaystyle C_{i}}$ est incorporé par son opérateur de projection ${\displaystyle P_{C_{i}}}$. Donc à chaque itération ${\displaystyle x}$ est mis à jour comme

${\displaystyle x_{k+1}=P_{C_{1}}P_{C_{2}}\cdots P_{C_{n}}x_{k}}$

Cependant, au-delà de ces problèmes, les opérateurs de projection ne sont pas appropriés et des opérateurs plus généraux sont nécessaires pour les résoudre. Parmi les diverses généralisations existantes de la notion d'opérateur de projection convexe, les opérateurs proximaux sont les mieux adaptés à d'autres fins.

Des instances spéciales de méthodes de gradient proximal sont

• Landweber projeté
• Projection alternée
• Méthode de multiplicateurs de Lagrange augmentée

• Opérateur proximal
• Méthodes de gradient proximal pour l'apprentissage
• Algorithme de Frank-Wolfe

• R. T. Rockafellar, Convex analysis, Princeton, Princeton University Press, 1970
• Patrick L. Combettes et Jean-Christophe Pesquet, Fixed-Point Algorithms for Inverse Problems in Science and Engineering, vol. 49, 2011, 185–212 p.

• Livre de Stephen Boyd et Lieven Vandenberghe, Optimisation convexe
• EE364a : Optimisation convexe I et EE364b : Optimisation convexe II, pages d'accueil des cours de Stanford
• EE227A : Notes de Lieven Vandenberghe Conférence 18
• ProximalOperators.jl : un package Julia implémentant des opérateurs proximaux.
• ProximalAlgorithms.jl : un package Julia implémentant des algorithmes basés sur l'opérateur proximal, y compris la méthode du gradient proximal.
• Référentiel Proximity Operator : une collection d'opérateurs de proximité implémentés dans Matlab et Python.

• Portail de la physique