La convexidad y por qué importa

Un valle, una respuesta

Una función es convexa si el segmento que une dos puntos de su gráfica queda sobre la gráfica o encima de ella: $f(\theta\mathbf x+(1-\theta)\mathbf y)\le\theta f(\mathbf x)+(1-\theta)f(\mathbf y)$ para todo $\theta\in[0,1]$. Para una función dos veces derivable hay una prueba práctica: $f$ es convexa exactamente cuando su hessiano es semidefinido positivo en todas partes, es decir, todos sus valores propios son $\ge0$. Las sumas de funciones convexas, sus múltiplos positivos y el máximo de funciones convexas vuelven a ser convexos, así se construyen objetivos convexos grandes a partir de piezas pequeñas.

La convexidad es lo que hace fiable la optimización. Todo mínimo local es un mínimo global, un gradiente nulo basta para parar, y la respuesta no depende de dónde empiece el solucionador. Si la función es estrictamente convexa el minimizador además es único, y si es fuertemente convexa, con curvatura de al menos $\mu>0$ en cada dirección, el descenso de gradiente converge a la velocidad geométrica vista antes. Sin convexidad nada de esto está garantizado: el solucionador puede parar en un valle que no es el más profundo.

En finanzas los objetivos convexos incluyen la varianza de cartera $\mathbf w^{T}\Sigma\mathbf w$ (una matriz de covarianza es semidefinida positiva), las pérdidas de mínimos cuadrados, la norma $\ell_1$ $\lVert\mathbf w\rVert_1$ y el expected shortfall (CVaR) como función de los pesos. El valor en riesgo, un tope al número de pesos no nulos y el ratio de Sharpe tal cual no son convexos. Una matriz de covarianza muestral estimada con menos observaciones que activos es semidefinida positiva pero singular, así que la varianza es convexa sin ser estrictamente convexa y muchos vectores de pesos empatan en el mínimo.

• Prueba del hessiano: todos los valores propios $\ge0$ en todas partes es convexa; un valor propio negativo, no convexa.
• Beneficio: todo mínimo local es global, así que el punto de partida no importa.
• Bloques: sumas, múltiplos positivos y máximos de funciones convexas siguen siendo convexos.

Lab: qué se califica

• Una brecha de convexidad15 pts
• El valor propio que rompe la convexidad15 pts
• Qué hessiano es convexo15 pts
• Objetivos convexos en finanzas15 pts
• Un gradiente nulo10 pts
• Vocabulario de convexidad15 pts
• Por qué a los solucionadores les gustan los problemas convexos15 pts