Convexidad y subgradientes · Definición
Subgradiente
Cuando una función convexa tiene esquinas o picos, el gradiente no existe en esos puntos. El subgradiente permite seguir usando ideas de optimización en esos casos.
Definición
El subgradiente es una generalización del gradiente para funciones convexas no diferenciables: en cada punto, es un vector g que define una cota inferior affine de f, es decir, f(y) ≥ f(x) + gᵀ(y − x) para todo y.
El conjunto de todos los subgradientes de f en x se llama subdiferencial, \( \partial f(x) \). Si f es diferenciable en x, el subdiferencial se reduce al único vector \( \{\nabla f(x)\} \). Además, para una función convexa el subdiferencial es siempre un conjunto convexo y no vacío en el interior de su dominio.
Consideremos \( f(x) = |x| \). En \( x = 0 \), el subdiferencial es el intervalo \( [-1, 1] \), porque cualquier pendiente en ese rango queda por debajo de la función. En \( x = 2 \), en cambio, \( \partial f(2) = \{1\} \), igual al gradiente.
Un error típico es pensar que el subgradiente debe ser único, como el gradiente. En puntos de no diferenciabilidad hay infinitos subgradientes, y elegir uno arbitrario no equivale a calcular la derivada, por lo que no basta con cualquier valor en un punto anguloso.
Para pensar
¿Por qué el subdiferencial de \( |x| \) en \( x = 0 \) no puede ser un único número?
Porque hay infinitas rectas que pasan por \( (0,0) \) y quedan por debajo de \( |x| \) (pendientes entre \( -1 \) y \( 1 \)), así que el conjunto tiene infinitos elementos.
Ejercicios 10
- ¿Cómo se llama el conjunto de todos los subgradientes de f en x?
- Si f es diferenciable en x, ¿qué subdiferencial tiene f en ese punto?
- Para f(x) = |x|, ¿cuál es el subdiferencial en x = 0?
- Si \( g_1 \) es subgradiente de f en \( x_1 \) y \( g_2 \) lo es en \( x_2 \), con f convexa, ¿qué desigualdad cumplen?
- ¿Qué significa que g sea un subgradiente de f en x?
- Para f(x) = max(x, 0), ¿cuál es el subdiferencial en x = 0?
- Para f(x) = 2|x| en x = 1, ¿cuál es el subdiferencial?
- Sea f(x) = |x| + x. ¿Cuál es el subdiferencial en x = 0?
- Para f(x) = |x - 3| en x = 3, ¿qué subdiferencial tiene f?
- Sea f(x) = max(x, 0) + max(-x, 0) · 2 para x en R. ¿Cuál es el subdiferencial en x = 0?
Después de esto
Referencias
- Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
- Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.