Optimización convexa — conceptos, métodos y aplicaciones

La optimización convexa consiste en minimizar una función convexa sobre un conjunto factible convexo. La razón principal por la que importa es simple: si se cumplen esas condiciones de convexidad, cualquier mínimo local también es un mínimo global.

Esa garantía hace que estos problemas sean mucho más fiables que los problemas de optimización generales. Aun así, hay que modelar el problema correctamente, pero una vez que el modelo es convexo, no estás persiguiendo una solución que solo parece la mejor en una pequeña vecindad.

Una forma común es

$$\text{minimize } f(x)$$

sujeto a

$$g_i(x) \le 0 \quad \text{for } i=1,\dots,m, \qquad Ax=b,$$

donde $f$ y cada $g_i$ son convexas, y las restricciones de igualdad son afines. Bajo esas condiciones, el conjunto factible es convexo y el problema de optimización es convexo.

Definición de optimización convexa

Una función $f$ es convexa si, para cualesquiera dos puntos $x$ e $y$ en su dominio y cualquier $0 \le t \le 1$,

$$f(tx + (1-t)y) \le t f(x) + (1-t) f(y).$$

En lenguaje sencillo, el segmento de recta entre dos puntos de la gráfica queda por encima de la gráfica. En una variable, muchas funciones convexas tienen forma de cuenco, pero la desigualdad es la prueba real.

Un conjunto es convexo si, siempre que contiene dos puntos, también contiene todos los puntos del segmento de recta entre ellos.

Necesitas ambas partes:

• una función objetivo convexa
• un conjunto factible convexo

Si falla cualquiera de las dos, el problema puede dejar de ser convexo.

Por qué la optimización convexa es más fácil de analizar

La optimización suele ser difícil porque puede haber muchos valles. Un algoritmo puede seguir mejorando la función objetivo y aun así detenerse en un punto que solo es el mejor localmente.

La optimización convexa elimina ese modo específico de fallo. Si la función objetivo es convexa y la región factible es convexa, entonces un punto que no puede mejorarse localmente ya es globalmente óptimo. Por eso los problemas convexos importan en estadística, aprendizaje automático, control e investigación de operaciones.

Esto no significa que todo problema convexo sea fácil. Algunos siguen siendo grandes o costosos computacionalmente. Significa que la estructura es lo bastante limpia como para que buenos algoritmos puedan apuntar al óptimo real en lugar de quedar atrapados por comportamientos locales engañosos.

Ejemplo resuelto de optimización convexa

Considera el problema sin restricciones

$$\text{minimize } f(x) = (x-3)^2 + 2.$$

Este es un problema de optimización convexa porque $f(x)$ es una cuadrática con coeficiente principal positivo, así que es convexa en todos los números reales.

Para encontrar el minimizador, derivamos:

$$f'(x) = 2(x-3).$$

Igualamos la derivada a cero:

$$2(x-3)=0 \quad \Rightarrow \quad x=3.$$

Ahora evaluamos la función objetivo:

$$f(3) = (3-3)^2 + 2 = 2.$$

Así, el valor mínimo es $2$, alcanzado en $x=3$.

Este ejemplo es simple, pero muestra la idea principal. Una vez que llegas a $x=3$, no hay un valle más bajo escondido en otra parte.

Métodos comunes para optimización convexa

El método depende de la estructura del problema.

Para problemas suaves sin restricciones o con restricciones simples, son comunes los métodos basados en gradiente porque moverse en contra del gradiente puede reducir la función objetivo.

Para muchos problemas convexos con restricciones, los métodos de punto interior se usan ampliamente porque manejan las restricciones de forma directa y a menudo funcionan bien en la práctica.

Para problemas convexos no suaves, los métodos de subgradiente o proximales pueden ser más apropiados. La idea importante no es la lista de algoritmos. Es la garantía de que la estructura convexa les da a esos algoritmos algo estable con lo que trabajar.

Errores comunes en optimización convexa

Suponer que una gráfica prueba la convexidad

Una gráfica puede parecer tener forma de cuenco en una representación y aun así no ser convexa en todo el dominio o en dimensiones superiores. La definición o las reglas estándar de convexidad importan más que un boceto.

Olvidar que las restricciones importan

Una función objetivo convexa por sí sola no basta. Si el conjunto factible no es convexo, el problema completo no es un problema de optimización convexa.

Tratar todo punto crítico como un mínimo

Para una función convexa diferenciable, un punto con gradiente cero es un minimizador global. Sin convexidad, esa conclusión no se cumple en general.

Confundir convexo con estrictamente convexo

La convexidad estricta es una condición más fuerte. A menudo da un minimizador único, mientras que la convexidad simple no siempre garantiza unicidad.

Dónde se usa la optimización convexa

La optimización convexa aparece siempre que un problema real puede modelarse con costos convexos y restricciones convexas.

Entre los ejemplos comunes están el ajuste por mínimos cuadrados, las máquinas de vectores de soporte, la selección de carteras bajo modelos de riesgo convexos y muchos problemas de asignación de recursos. El modelo exacto importa: una aplicación es convexa solo cuando la función objetivo y las restricciones elegidas realmente satisfacen las hipótesis de convexidad.

Cuándo ayuda la convexidad en la práctica

La optimización convexa es especialmente útil cuando necesitas más que un simple número. A menudo quieres una garantía de que la respuesta es realmente óptima para el modelo que escribiste.

Esa garantía importa en ingeniería y en el trabajo con datos porque separa dos preguntas:

1. ¿Resolvimos correctamente el problema matemático?
2. ¿Era el problema matemático un buen modelo de la realidad?

La convexidad ayuda mucho con la primera pregunta. No resuelve automáticamente la segunda.

Prueba un problema similar

Toma $f(x) = (x+1)^2 + 5$ y encuentra su mínimo. Luego compáralo con $f(x) = -(x+1)^2 + 5$, que es cóncava, no convexa. Esa comparación lado a lado hace mucho más fácil ver el papel de la convexidad.

Si quieres explorar otro caso, intenta plantear un pequeño problema de mínimos cuadrados y observa cómo minimizar una función de error convexa conduce a un mejor ajuste estable.