Método del gradiente proximal

Los métodos de gradiente proximal son una forma generalizada de proyección que se utiliza para resolver problemas de optimización convexa no diferenciables .

Muchos problemas interesantes pueden formularse como problemas de optimización convexa de la forma

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

dónde${\displaystyle f_{i}:\mathbb {R} ^{d}\rightarrow \mathbb {R} ,\ i=1,\dots ,n}$Son posiblemente funciones convexas no diferenciables . La falta de diferenciabilidad descarta las técnicas convencionales de optimización suave, como el método del descenso más pronunciado y el método del gradiente conjugado , pero en su lugar se pueden utilizar métodos de gradiente proximal.

Los métodos de gradiente proximal comienzan con un paso de división, en el que las funciones${\displaystyle f_{1},...,f_{n}}$se utilizan individualmente para producir un algoritmo fácilmente implementable . Se llaman proximales porque cada función no diferenciable entre${\displaystyle f_{1},...,f_{n}}$está involucrado a través de su operador de proximidad . El algoritmo iterativo de umbralización de contracción, ^{[ 1 ]} Landweber proyectado , gradiente proyectado, proyecciones alternas , método de multiplicadores de dirección alterna , Bregman dividido alternado son instancias especiales de algoritmos proximales. ^{[ 2 ]}

Para la teoría de los métodos de gradiente proximal desde la perspectiva de y con aplicaciones a la teoría del aprendizaje estadístico , véase métodos de gradiente proximal para el aprendizaje .

Uno de los algoritmos de optimización convexa más utilizados es el de proyecciones sobre conjuntos convexos (POCS). Este algoritmo se emplea para recuperar/sintetizar una señal que satisfaga simultáneamente varias restricciones convexas.${\displaystyle f_{i}}$sea ​​la función indicadora del conjunto convexo cerrado no vacío${\displaystyle C_{i}}$modelar una restricción. Esto se reduce a un problema de factibilidad convexa, que requiere que encontremos una solución tal que se encuentre en la intersección de todos los conjuntos convexos.${\displaystyle C_{i}}$. En el método POCS cada conjunto${\displaystyle C_{i}}$está incorporada por su operador de proyección${\displaystyle P_{C_{i}}}$. Entonces, en cada iteración${\displaystyle x}$se actualiza como

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

Sin embargo, más allá de estos problemas, los operadores de proyección no son apropiados y se requieren operadores más generales para abordarlos. Entre las diversas generalizaciones del concepto de operador de proyección convexa que existen, los operadores proximales son los más adecuados para otros fines.

Los casos especiales de métodos de gradiente proximal son:

• Landweber proyectado
• Proyección alternada
• Método de multiplicadores de dirección alterna

• Operador proximal
• Métodos de gradiente proximal para el aprendizaje
• Algoritmo de Frank-Wolfe

• Rockafellar, RT (1970). Análisis convexo . Princeton: Princeton University Press.
• Combettes, Patrick L.; Pesquet, Jean-Christophe (2011). Algoritmos de punto fijo para problemas inversos en ciencia e ingeniería . Vol.  49. pp. 185–212 . 

• Libro de Stephen Boyd y Lieven Vandenberghe, Optimización convexa
• EE364a: Optimización Convexa I y EE364b: Optimización Convexa II , páginas web de los cursos de Stanford
• EE227A: Lieven Vandenberghe Notas Conferencia 18
• ProximalOperators.jl : un paquete de Julia que implementa operadores proximales.
• ProximalAlgorithms.jl : un paquete de Julia que implementa algoritmos basados ​​en el operador proximal, incluido el método del gradiente proximal.
• Repositorio de operadores de proximidad : una colección de operadores de proximidad implementados en Matlab y Python .