Optimización Convexa

Un conjunto $C$ es convexo si para cualesquiera $\mathbf{x}, \mathbf{y} \in C$ y $t \in [0, 1]$, la combinación convexa $t\mathbf{x} + (1-t)\mathbf{y}$ también está en $C$ — el segmento entre cualesquiera dos puntos se queda dentro. Una función $f$ es convexa si $f(t\mathbf{x} + (1-t)\mathbf{y}) \leq tf(\mathbf{x}) + (1-t)f(\mathbf{y})$: la gráfica está debajo de cualquier cuerda que une dos puntos.

Condiciones equivalentes para $f$ dos veces diferenciable: $f$ es convexa si y solo si su hessiano es semidefinido positivo en todas partes. Lineales, cuadráticas con matriz PSD, exponenciales, $-\log$, máximo de afines y muchas otras son convexas. La clase es cerrada bajo combinaciones lineales no negativas, máximos puntuales y cambios afines de dominio — así puedes construir funciones convexas complejas a partir de piezas simples.

El superpoder de la optimización convexa es este: todo mínimo local es mínimo global, y los métodos basados en gradiente convergen (a menudo a tasas conocidas) a ese óptimo global. Sin puntos de silla, sin trampas locales, sin preocupaciones por la inicialización. Si puedes plantear tu problema como convexo, esencialmente lo has resuelto — por eso se invierte tanto esfuerzo en encontrar formulaciones convexas.

Problemas convexos clásicos incluyen mínimos cuadrados (objetivo cuadrático convexo), regresión logística (log-pérdida convexa), regresión Lasso y Ridge (objetivos convexos con regularizadores convexos), SVMs (programa cuadrático convexo) y programación lineal. Los solucionadores convexos modernos (CVX, SCS, MOSEK) pueden manejar problemas con millones de variables. Campos enteros — optimización de portafolios, flujo en redes, compressed sensing — están construidos sobre fundamentos convexos.

El entrenamiento de redes neuronales es famosamente no convexo — el paisaje de la pérdida tiene innumerables mínimos locales y puntos de silla. Y aun así las redes neuronales se entrenan consistentemente a buenas soluciones vía SGD, que es uno de los grandes misterios del deep learning. El trabajo teórico sugiere que la sobre-parametrización crea paisajes benignos donde la mayoría de los mínimos locales son casi tan buenos como el global, y que la dinámica de SGD prefiere mínimos 'planos' que generalizan. Incluso en este régimen no convexo, las intuiciones del análisis convexo — suavidad de Lipschitz, convexidad fuerte, dualidad — siguen siendo guías.

Ejemplo trabajado — prueba del hessiano en 2D: Para $f(x,y) = x^2 + 4xy + 5y^2$, $H = \begin{pmatrix}2 & 4 \\ 4 & 10\end{pmatrix}$. Los autovalores de $(\lambda - 2)(\lambda - 10) - 16 = 0$ dan $\lambda^2 - 12\lambda + 4 = 0$, así $\lambda = 6 \pm \sqrt{32} \approx 0.343$ y $11.66$. Ambos positivos, así $f$ es convexa — la prueba del hessiano lo confirma rápido.