Méthode du gradient proximal

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.

Une comparaison entre les itérations de la méthode du gradient projeté (en rouge) et de la méthode Frank-Wolfe (en vert).

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

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

où $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 $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 $f_{1},...,f_{n}$ intervient via son opérateur proximal . L'algorithme itératif avec seuil de retrait, 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.

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.

Projection sur des ensembles convexes (POCS)

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 $f_{i}$ la fonction indicatrice d'un ensemble convexe fermé non vide $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. $C_{i}$. Dans la méthode POCS, chaque ensemble $C_{i}$ est incorporé par son opérateur de projection $P_{C_{i}}$. Donc à chaque itération $x$ est mis à jour comme

$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.

Exemples

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

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

Voir également

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

Références

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

Liens externes

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