Método de 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 .

Una comparación entre las iteraciones del método del gradiente proyectado (en rojo) y el método de Frank-Wolfe (en verde).

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

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

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

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

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

Proyección sobre conjuntos convexos (POCS)

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

${\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 que existen de la noción de operador de proyección convexa, los operadores proximales son los más adecuados para otros fines.

Ejemplos

Ejemplos especiales de métodos de gradiente proximal son

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

Ver también

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

Notas

1. Daubechies, yo; Defrise, M; De Mol, C (2004). "Un algoritmo de umbral iterativo para problemas lineales inversos con una restricción de escasez". Comunicaciones sobre Matemática Pura y Aplicada . 57 (11): 1413-1457. arXiv : matemáticas/0307152 . Código Bib : 2003 matemáticas ...... 7152D. doi :10.1002/cpa.20042.
2. Los detalles de los métodos proximales se analizan en Combettes, Patrick L.; Pesquet, Jean-Christophe (2009). "Métodos de división proximal en el procesamiento de señales". arXiv : 0912.3522 [matemáticas.OC].

Referencias

• Rockafellar, RT (1970). Análisis convexo . Princeton: Prensa de la Universidad de Princeton.
• Combettes, Patrick L.; Pesquet, Jean-Christophe (2011). Algoritmos de punto fijo para problemas inversos en ciencia e ingeniería . vol. 49, págs. 185-212.

enlaces externos

• Libro de Stephen Boyd y Lieven Vandenberghe, Optimización convexa
• EE364a: Optimización convexa I y EE364b: Optimización convexa II, páginas de inicio de 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 de gradiente proximal.
• Repositorio de operadores de proximidad: una colección de operadores de proximidad implementados en Matlab y Python .