La clave del algoritmo proximal es el operador proximal.
¿Qué es el operador proximal?
El operador proximal es equivalente al gradiente implícito (o Euler hacia atrás). La actualización de gradiente no está utilizando el (sub) gradiente estimado en el punto actual [matemática] x ^ k [/ matemática]. En cambio, encuentra el (sub) gradiente en el siguiente punto [matemática] x ^ {k + 1} [/ matemática].
Gradiente implícito / hacia atrás Euler se calcula resolviendo:
[matemáticas] x ^ {k + 1} = x ^ k – \ lambda \ nabla f (x ^ {k + 1}) [/ matemáticas]
- ¿Los desarrolladores de Google realmente usan conceptos como la notación O grande para determinar el tiempo de ejecución de un algoritmo en un proceso de codificación diario?
- ¿Cuál es la probabilidad de que un determinado número binario de 6 bits divida perfectamente un binario aleatorio de 15 bits?
- ¿Cómo debería uno prepararse para los problemas en los árboles en la programación competitiva?
- Dado un componente fuertemente conectado, ¿puede determinar en tiempo lineal si la eliminación de un solo nodo convierte el SCC en un gráfico acíclico dirigido?
- ¿Dónde y cómo puedo aprender sobre la creación / comprensión de algoritmos de negociación de acciones?
En comparación, el descenso de gradiente explícito / Euler hacia adelante se da como:
[matemáticas] x ^ {k + 1} = x ^ k – \ lambda \ nabla f (x ^ k) [/ matemáticas]
Echemos un vistazo a la actualización proximal de [math] x ^ k [/ math]:
[matemáticas] \ textbf {prox} _f (x ^ k) = \ text {argmin} f (x) + \ frac {1} {2 \ lambda} || x – x ^ k || ^ 2 [/ matemáticas]
La condición óptima viene dada por:
[matemáticas] 0 = \ lambda \ nabla f (x ^ *) + (x ^ * – x ^ k) [/ matemáticas]
Tenga en cuenta que [math] x ^ * = x ^ k – \ lambda \ nabla f (x ^ *) [/ math] es exactamente la actualización proximal.
Ahora, volvamos al algoritmo mismo. El algoritmo proximal es solo una serie de pasos de actualización iterativos para encontrar el siguiente punto de reparación:
[matemáticas] x ^ * = \ textbf {prox} _f (x ^ *) [/ matemáticas]
¿Cuándo es útil el algoritmo proximal?
El algoritmo proximal es una gran herramienta para resolver problemas de optimización no uniformes, restringidos, a gran escala o distribuidos. Una aplicación particular del algoritmo proximal en el problema primario-dual es que actualiza secuencialmente las variables primarias y duales para encontrar el punto de apoyo de la función de energía.
Referencias
1. [Un tutorial muy útil de UCLA] http://www.math.ucla.edu/~wotaoy…
2. Algoritmos proximales, N. Parikh, S. Boyd
