Para una función convexa $h$ su operador proximal se define como $$\operatorname{prox}_h(x)=\arg\min_u \Big(h(u)+\frac{1}{2}\|u-x\|^2\Big)$$ ¿Puede alguien dar una explicación/motivación intuitiva de la cartografía proximal?
Respuestas
¿Demasiados anuncios?
Moormanly
Puntos
151
He aquí dos interpretaciones que pueden dar una intuición útil en algunas circunstancias:
Prox es una proyección generalizada
Considere el indicador de algún conjunto convexo no vacío $X$ : $$i_X(x) = \begin{cases}0 & \text{if } x \in X \\ \infty & \text{if } x \not \in X\end{cases}.$$ Entonces encontramos que el mapeo proximal es la proyección sobre $X$ : $$\begin{align}\text{prox}_{\alpha i_X}(y) &= \underset{x}{\text{argmin}}(\alpha i_X(x)+\frac{1}{2}\|x - y\|^2) \\ &= \underset{x \in X}{\text{argmin}}(\frac{1}{2}\|x - y\|^2) \\ &= \text{proj}_X(y).\end{align}$$
Prox es Euler hacia atrás
Consideremos la actualización de Euler hacia atrás: $x^{k+1} = x^k - \alpha \nabla f(x^{k+1})$ para alguna diferenciable $f$ . Esta actualización puede ser vista como una actualización de punto proximal $x^{k+1} = \text{prox}_{\alpha f}(x^k)$ ya que para funciones convexas diferenciables la condición de optimalidad es $0 = \nabla (\alpha f(x^\star) + \frac{1}{2}\|x^\star - x^k\|^2) = \alpha \nabla f(x^\star) + x^\star - x^k$ .
littleO
Puntos
12894
Si $h$ es una función convexa cerrada, entonces el operador proximal de $h$ (con el parámetro $t > 0$ ) se define por $$ \text{prox}_{th}(\hat x) = \arg \min_x \, h(x) + \frac{1}{2t} \|x - \hat x \|_2^2. $$ Cuando evaluamos el operador prox de $h$ se trata de reducir el valor de $h$ pero se nos penaliza por alejarnos demasiado de $\hat x$ . (El parámetro $t$ es como un "tamaño de paso" que controla cuánto se nos penaliza por alejarnos de $\hat x$ .)
Puede ver que la evaluación de un operador prox puede ser un subpaso útil en un algoritmo de optimización. Por ejemplo, supongamos que queremos resolver el problema de optimización $$ \text{minimize} \quad g(x) + h(x) $$ donde $g$ y $h$ son convexos, $g$ es diferenciable, y $h$ es "simple" en el sentido de que su operador prox puede ser evaluado eficientemente. (Es importante, $h$ est no que se requiere para ser diferenciable). Una estrategia natural es reducir primero el valor de $g$ dando un paso en la dirección del gradiente negativo, y luego reducir el valor de $h$ aplicando el operador prox de $h$ y repite. Esta estrategia produce la siguiente iteración: $$ x^{k+1} = \text{prox}_{th}(x^k - t \nabla g(x^k)). $$ (Esta iteración se conoce como el método del gradiente proximal. Podrías implementarlo ahora mismo en Python para resolver famosos problemas de optimización como el problema de Lasso de la estadística).
Aquí hay una forma alternativa de derivar el método del gradiente proximal y, en el proceso, descubrir el operador proximal. Supongamos de nuevo que queremos minimizar $g(x) + h(x)$ con $g$ y $h$ como se ha indicado anteriormente. Una estrategia natural es sustituir $g$ con una aproximación lineal local a $g$ (esta es la estrategia fundamental del cálculo), y también añadir un término de penalización a la función objetivo que nos penaliza por alejarnos demasiado del iterado actual (esto asegura que la aproximación lineal local a $g$ sigue siendo exacta). Esta estrategia da lugar a la siguiente iteración: $$ x^{k+1} = \arg \min_x \quad h(x) + \underbrace{g(x^k) + \nabla g(x^k)^T(x - x^k)}_{\approx \, g(x)} + \frac{1}{2t} \|x - x^k \|_2^2. $$ Ahora, si combinamos los dos términos de la derecha por completando el cuadrado y luego omitir los términos que no dependen de $x$ encontramos que \begin{align} x^{k+1} &= \arg \min_x \, h(x) + \frac{1}{2t} \|x - (x^k - t\nabla g(x^k)) \|_2^2 \\ &= \text{prox}_{th}(x^k - t\nabla g(x^k)). \end{align} Esta es la iteración del gradiente proximal. Vemos que el operador proximal de $h$ ha aparecido de la nada. A mí me parece la forma más probable de que alguien descubra la idea de un operador próximo.
Otra motivación para el operador proximal viene del punto de vista de la teoría de operadores monótonos. La minimización de una función convexa cerrada $h$ equivale a encontrar un punto $x$ tal que $$ \tag{1} 0 \in \partial h(x). $$ Aquí $\partial h(x)$ es el subdiferencial de $h$ en $x$ . El mapeo de valor de conjunto $x \mapsto \partial h(x)$ es el mejor ejemplo de un "operador monótono", y el problema (1) se denomina "problema de inclusión monótona". Multiplicando ambos lados por $t$ y luego añadir $x$ a ambos lados, encontramos que \begin{align} & 0 \in \partial h(x) \\ \iff & x \in (I + t \partial h)(x) \\ \iff & x \in (I + t \partial h)^{-1}(x). \end{align} El operador $(I + t \partial h)^{-1}$ se llama el "resolvente" del operador $\partial h$ y tiene buenas propiedades como las siguientes: si $x \in \mathbb R^n$ entonces $(I + t \partial h)^{-1}(x)$ es un singleton. Por lo tanto, $(I + t \partial h)^{-1}$ puede ser visto como un función (en lugar de un mapeo de valor de conjunto), y resolver $0 \in \partial h(x)$ equivale a resolver
$$ x = (I + t \partial h)^{-1}(x). $$ Una idea natural es resolver para $x$ utilizando la iteración de punto fijo. La iteración resultante es $$ x^{k+1} = (I + t \partial h)^{-1}(x^k). $$
La línea de golpe: La función $(I + t \partial h)^{-1}$ no es otro que el operador proximal de $h$ y esta iteración se conoce como el "algoritmo del punto proximal".
protolyse
Puntos
26
Ya hay muchas respuestas buenas aquí, pero en aras de la exhaustividad añadiré más intuiciones. El operador proximal de $g$ (con el parámetro $\lambda$ ) también puede verse como un paso de gradiente (con tamaño de paso $\lambda$ ) con respecto a la envolvente de Moreau $g_\lambda$ de $g$ . La envolvente de Moreau es una subaproximación suave de la función original y viene dada por $$ g_\lambda(x) = \min_u \{g(u) + \frac{1}{2 \lambda} || u-x||^2\}. $$ Evidentemente, su definición está estrechamente relacionada con el operador proximal. La identidad antes mencionada se lee entonces como $$ \operatorname{prox}_{\lambda g}(x) = x - \lambda \nabla g_\lambda(x). $$
