Programación lineal y proximal · Definición

Método de gradiente proximal

optimización continuaprogramación lineal y proximal

Antes de empezar necesitas conocer

Cuando una parte del objetivo es suave y otra no lo es, conviene tratar cada una por separado. Este método combina ambas ideas en una sola iteración.

Definición

El gradiente proximal minimiza \( f(x)+g(x) \), con \( f \) convexa y suave y \( g \) convexa posiblemente no diferenciable, alternando un paso de gradiente en \( f \) y un paso proximal en \( g \).

\[x_{k+1}=\operatorname{prox}_{t_k g}\left(x_k-t_k\nabla f(x_k)\right)\]

Si \( f \) tiene gradiente \( L \)-Lipschitz y \( g \) es convexa y cerrada, con paso \( t \in (0, 1/L] \) la sucesión generada cumple \( F(x_k)-F^* \le \frac{\|x_0-x^*\|^2}{2tk} \), donde \( F=f+g \). Cuando \( g=0 \) el método se reduce al descenso de gradiente clásico, y cuando \( f=0 \) se reduce al algoritmo del punto proximal.

Consideremos minimizar \( \tfrac12\|Ax-b\|^2+\lambda\|x\|_1 \). Aquí \( f(x)=\tfrac12\|Ax-b\|^2 \) tiene gradiente \( A^\top(Ax-b) \), y \( g(x)=\lambda\|x\|_1 \) tiene prox dado por el umbral suave componente a componente. Cada iteración hace un paso de gradiente en \( f \) y luego aplica el umbral, produciendo soluciones dispersas.

Un error típico es aplicar el paso de gradiente también sobre \( g \), es decir, derivar \( \|x\|_1 \) donde no existe. Esto impide usar el método cuando \( g \) tiene puntos angulosos. La regla correcta es evaluar el gradiente solo en \( f \) y dejar \( g \) para el operador proximal.

Para pensar

¿Por qué no se puede tomar el gradiente de \( g \) en \( x=0 \) cuando \( g(x)=|x| \)?

Porque \( |x| \) no es diferenciable en \( 0 \), así que no existe gradiente y por eso \( g \) se trata con el operador proximal.

Ejercicios 10

  1. ¿Qué función \( g \) aparece en el método de gradiente proximal para minimizar \( f(x)+g(x) \) cuando \( f \) es suave?
  2. ¿Qué operación se realiza sobre \( g \) en cada iteración del método?
  3. Si \( g=0 \), ¿a qué método se reduce el gradiente proximal?
  4. ¿Qué condición debe cumplir el gradiente de \( f \) para que el método tenga garantías de convergencia estándar?
  5. Para \( g(x)=\lambda\|x\|_1 \), ¿qué produce el operador proximal componente a componente?
  6. Si \( f(x)=\tfrac12\|x-a\|^2 \) y \( g=0 \), ¿cuál es el resultado de un paso con \( t=1 \) desde \( x_k \)?
  7. Si \( g(x)=\lambda|x| \) en una dimensión y el punto \( z=0.3 \) con \( t\lambda=0.5 \), ¿cuál es \( \operatorname{prox}_{tg}(z) \)?
  8. Con \( f(x)=\tfrac12 x^2 \) y \( g(x)=|x| \) en una dimensión, ¿cuál es la sucesión después de un paso con \( t=1 \) desde \( x_0=4 \)?
  9. ¿Cuál de las siguientes afirmaciones sobre la cota \( F(x_k)-F^*\le \frac{\|x_0-x^*\|^2}{2tk} \) es correcta?
  10. Minimizar \( \tfrac12(x-6)^2+|x| \) en \( \mathbb{R} \) con un paso de gradiente proximal con \( t=1 \) desde \( x_0=0 \). ¿Cuál es \( x_1 \)?

Referencias

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
  • Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.