Programación lineal y proximal · Definición

Operador proximal

optimización continuaprogramación lineal y proximal

Antes de empezar necesitas conocer

Cuando una función no es derivable en todos sus puntos, el descenso de gradiente clásico no sirve directamente. El operador proximal resuelve este obstáculo combinando la función con un término cuadrático que mantiene la solución cerca del punto de partida.

Definición

El operador proximal de una función convexa \( f \) asigna a cada punto \( x \) el único minimizador de \( f(u)+\frac{1}{2}\|u-x\|^2 \).

\[\operatorname{prox}_{f}(x)=\arg\min_{u}\left\{f(u)+\tfrac{1}{2}\|u-x\|^2\right\}\]

Para \( f \) convexa, cerrada y propia, el problema de minimización tiene solución única porque el término \( \frac{1}{2}\|u-x\|^2 \) es estrictamente convexo. Además, \( \operatorname{prox}_{f}(x) \) se caracteriza por la condición \( x-\operatorname{prox}_{f}(x)\in\partial f(\operatorname{prox}_{f}(x)) \), donde \( \partial f \) es el subdiferencial.

Si \( f(u)=\lambda|u| \) en \( \mathbb{R} \), el operador proximal es la función de umbral suave: \( \operatorname{prox}_{f}(x)=\operatorname{sign}(x)\max(|x|-\lambda,0) \). Para \( x=3 \) y \( \lambda=1 \) resulta \( 2 \), que es el punto donde se equilibran el término de penalización y la distancia a \( x \).

Un error típico es olvidar el factor \( \frac{1}{2} \) en el término cuadrático, lo que cambia el operador y produce resultados incorrectos. Otro error frecuente es confundir el operador proximal con la proyección: la proyección es el caso particular en que \( f \) es la indicatriz de un conjunto convexo.

Para pensar

Si \( f \) no fuera convexa, ¿por qué podría dejar de definirse \( \operatorname{prox}_{f} \) como función?

Porque el problema puede tener varios minimizadores, así que el resultado sería un conjunto de puntos y no uno solo.

Ejercicios 10

  1. ¿Cuál es el valor de \( \operatorname{prox}_{f}(x) \) para \( f(u)=0 \)?
  2. Para \( f(u)=\frac{1}{2}u^2 \), ¿cuál es el operador proximal de \( x \)?
  3. ¿Cuál es el operador proximal de \( x \) cuando \( f(u)=|u| \) y \( x=0.5 \)?
  4. ¿Qué conjunto de condiciones caracteriza \( p=\operatorname{prox}_{f}(x) \)?
  5. ¿Cuál es el valor de \( \operatorname{prox}_{f}(x) \) si \( f(u)=2u \) y \( x=1 \)?
  6. Para \( f(u)=\lambda|u| \) con \( \lambda=2 \), ¿cuál es \( \operatorname{prox}_{f}(-5) \)?
  7. Si \( f(u)=\frac{1}{2}u^2 \) y \( x=4 \), ¿cuál es \( \operatorname{prox}_{f}(x) \)?
  8. Para \( f(u)=|u| \) y \( x=-0.5 \), ¿cuál es \( \operatorname{prox}_{f}(x) \)?
  9. ¿Cuál es \( \operatorname{prox}_{f}(x) \) para \( f(u)=\lambda|u| \) con \( \lambda=1 \) y \( x=0.8 \)?
  10. Sea \( f(u)=\lambda|u| \) con \( \lambda=1 \). Calcula \( \operatorname{prox}_{f}(x) \) para \( x=-2.5 \) y decide cuál de estas afirmaciones es verdadera al comprobar la condición \( x-p\in\partial f(p) \).

Referencias

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