Optimización no lineal con restricciones, las condiciones que esconden el óptimo

Imagen de Mariola Grobelska extraída de Unsplash

Cuando nos adentramos en el mundo de la optimización matemática no lineal, el primer instinto suele ser recurrir a las herramientas que aprendimos en cálculo básico. Si queremos encontrar el mínimo o máximo de una función, derivamos e igualamos a cero. Sin embargo, en el mundo real, la optimización casi siempre viene acompañada de restricciones.

¿Por qué los métodos básicos no son suficientes?

En un problema de optimización sin restricciones, el teorema de Fermat nos dice que basta con buscar los puntos donde el gradiente de la función objetivo se anula ($\nabla f(x) = \mathbf{0}$).

Si añadimos restricciones de igualdad (por ejemplo, $h(x) = 0$), el método de los Multiplicadores de Lagrange acude al rescate. Este método nos permite construir una función auxiliar (el Lagrangiano) y resolver el sistema asumiendo que el gradiente de la función objetivo debe ser paralelo al de las restricciones.

Pero, ¿qué sucede cuando nos enfrentamos a restricciones de desigualdad ($g(x) \leqslant 0$)?

Aquí es donde los métodos básicos colapsan. Una restricción de desigualdad introduce una complicación enorme: la solución óptima podría estar en el interior de la región factible (haciendo que la restricción sea irrelevante o inactiva) o justo en el límite de la misma (haciendo que la restricción sea activa). Los multiplicadores de Lagrange puros no pueden manejar esta dualidad condicional, ni pueden garantizarnos la dirección correcta del gradiente en las fronteras. Por todo ello, necesitamos un marco más robusto.

El descubrimiento (y redescubrimiento) de KKT

El marco teórico que resolvió este problema se conoce hoy como las Condiciones de Karush-Kuhn-Tucker (KKT), pero el nombre esconde una historia de justicia matemática que vale la pena contar.

Tal como relata Richard W. Cottle en su ensayo “William Karush and the KKT theorem” (incluido en el magnífico libro divulgativo Optimization Stories (Grötschel, 2012)), la comunidad matemática reconoció durante décadas este avance bajo el nombre de Condiciones de Kuhn-Tucker. Harold W. Kuhn y Albert W. Tucker presentaron estos resultados en 1950 durante el Segundo Simposio de Berkeley sobre Estadística Matemática y Probabilidad, publicándolos con gran éxito en 1951 (Kuhn & Tucker, 1951).

Sin embargo, William Karush se les había adelantado 11 años. En 1939 (Karush, 1939) Karush desarrolló exactamente las mismas condiciones como parte de su trabajo fin de máster en la Universidad de Chicago. Desafortunadamente, al tratarse de un documento no publicado y debido a la irrupción de la Segunda Guerra Mundial, su trabajo quedó sepultado en los archivos y pasó desapercibido para el mundo académico. No fue hasta varias décadas después que se descubrió su contribución original, enmendando el nombre oficial del teorema a KKT para darle el crédito que legítimamente merecía.

El paso intermedio, las condiciones de Fritz John

Antes de llegar a las condiciones KKT, en 1948 (John, 1948), el matemático Fritz John formuló un resultado general basándose en esta geometría. Supongamos que queremos minimizar $f(\mathbf{x})$ sujeto a restricciones de desigualdad $g_i(\mathbf{x}) \leqslant 0$.

John demostró que si $x^*$ es un óptimo local, entonces existen multiplicadores $u_0, u_1, \ldots, u_m \geqslant 0$, no todos nulos, tales que:

\[u_0 \nabla f(\mathbf{x}^*) + \sum_{i=1}^m u_i \nabla g_i(\mathbf{x}^*) = \mathbf{0}\]

además de las condiciones de holgura complementaria ($u_i g_i(\mathbf{x}^*) = 0, \; \forall i \in \{1,\ldots,m\}$).

¿Cuál es el inconveniente de las condiciones de Fritz-John?

Si nos fijamos en el multiplicador $u_0$ que acompaña al gradiente de la función objetivo, éste puede ser $u_0 = 0$, en cuyo caso, el término de la función objetivo desaparece por completo. En este escenario (conocido como caso degenerado), las condiciones de optimización dependen únicamente de la geometría de las restricciones, ignorando lo que estamos intentando optimizar. Esto ocurre cuando la región factible tiene picos o singularidades extrañas.

En el camino hacia el óptimo, la geometría de las restricciones cuenta

Para entender cómo encontramos el punto óptimo en un problema con restricciones, imagina que estás caminando por un paisaje montañoso intentando llegar al punto más bajo posible (minimizando una función objetivo $f(\mathbf{x})$). Si no hubiera obstáculos, simplemente caminarías hacia abajo siguiendo la pendiente hasta llegar al fondo del valle, donde la inclinación es cero ($\nabla f(\mathbf{x}) = \mathbf{0}$).

Sin embargo, en nuestro problema existen “vallas” o topes que restringen por dónde puedes caminar (las restricciones de desigualdad $g_i(\mathbf{x}) \leqslant 0, \; i \in \{1,\ldots,m\}$).

¿Qué ocurre cuando llegas al punto más bajo permitido pero estás chocando contra una valla? En ese punto óptimo, tu deseo de seguir bajando (el gradiente de tu función) choca frontalmente contra la valla (el gradiente de la restricción). Si pudieras moverte sin cruzar la barrera, lo harías para seguir descendiendo. Sin embargo, como no puedes, significa que las fuerzas están en equilibrio. Matemáticamente, la dirección de máxima caída de tu función objetivo está perfectamente alineada (pero en sentido opuesto) a la dirección en la que la valla te empuja hacia adentro.

Para que la frontera de la región factible se comporte de manera adecuada y no se generen singularidades es necesario que las restricciones sean diferenciables y cumplan propiedades de convexidad o cuasiconvexidad.

Las Condiciones de Karush-Kuhn-Tucker (KKT)

Traduciendo esta intuición geométrica del equilibrio al lenguaje matemático riguroso, obtenemos las Condiciones KKT para problemas con desigualdades.

Para que un punto $\mathbf{x}^*$ sea una solución óptima local, se debe garantizar la existencia de los multiplicadores $\mathbf{u}$ (nuestras fuerzas de reacción de las vallas) cumpliendo las siguientes condiciones fundamentales:

Estacionariedad (El equilibrio de fuerzas): El gradiente de la función objetivo más los gradientes de las restricciones (multiplicados por su respectiva fuerza $u_i$) se anulan entre sí. Ninguna dirección permitida mejora el resultado.
\[\nabla f(\mathbf{x}^*) + \sum_{i=1}^m u_i \nabla g_i(\mathbf{x}^*) = \mathbf{0}\]
Factibilidad Primal (Respetar las reglas): El punto debe estar dentro de la región factible. No podemos cruzar las vallas.
\[g_i(\mathbf{x}^*) \leqslant 0, \quad \forall i \in \{1,\ldots,m\}\]
Factibilidad Dual (Las fuerzas sólo empujan, no tiran): Los multiplicadores (las vallas que no puedes cruzar) deben ser positivos o cero. La valla te empuja hacia adentro de la zona permitida para que no salgas, pero nunca te arrastra hacia afuera.
\[u_i \geqslant 0, \quad \forall i \in \{1,\ldots,m\}\]
Holgura Complementaria (Sólo importan las vallas que tocas): Si en tu punto óptimo no estás tocando una restricción concreta (es decir, $g_i(\mathbf{x}^*) < 0$), esa valla no está ejerciendo ninguna fuerza sobre ti, por lo que su multiplicador debe ser cero ($u_i = 0$). Sólo las restricciones “activas” participan en el equilibrio.
\[u_i g_i(\mathbf{x}^*) = 0, \quad \forall i \in \{1,\ldots,m\}\]
Independencia Lineal de las Restricciones Activas (Regularidad): Los gradientes de aquellas restricciones que se cumplen exactamente en la frontera en el punto óptimo (restricciones activas, $g_i(\mathbf{x}^*) = 0$) deben ser linealmente independientes:
\[\{\nabla g_i(\mathbf{x}^*)\}_{i \in \mathcal{I}}\]
es linealmente independiente, donde $\mathcal{I}(\mathbf{x}^*) = \{i \in \{1,\ldots,m\} : g_i(\mathbf{x}^*) = 0\}$.

Nota para problemas de maximización:

Si el problema es de maximización$f(\mathbf{x})$ manteniendo la ecuación de estacionariedad con signo positivo ($+\sum u_i \nabla g_i$), la condición de factibilidad dual cambia a $u_i \leqslant 0$. Esto se debe a que el gradiente de la función objetivo ($\nabla f$) apunta en el mismo sentido que el de la restricción ($\nabla g_i$).

¿Por qué funcionan estas condiciones? El papel de Farkas y Gordan

La validez de las condiciones KKT se asienta sobre los Teoremas de alternativa de la geometría convexa, principalmente el Lema de Gordan (1873) (Gordan, 1873) y el Lema de Farkas (1902) (Farkas, 1902).

En esencia, el Lema de Farkas establece una disyuntiva geométrica en $\mathbf{x}^*$:

O bien existe una dirección $d$ tal que podemos reducir el valor de la función objetivo, $\nabla f(\mathbf{x}^*)^\intercal d < 0$, manteniendo la factibilidad $\nabla g_i(\mathbf{x}^*)^\intercal d \leqslant 0$,
O bien el vector $-\nabla f(\mathbf{x}^*)$ pertenece al cono convexo generado por los gradientes de las restricciones activas $\{\nabla g_i(\mathbf{x}^*)\}_{i \in \mathcal{I}}$.

Como $\mathbf{x}^*$ es un mínimo local, no puede existir ninguna dirección de descenso factible. Por lo tanto, el Lema de Farkas garantiza matemáticamente que $-\nabla f(\mathbf{x}^*)$ debe expresarse como una combinación lineal con coeficientes no negativos ($u_i \geqslant 0$) de los gradientes $\nabla g_i(\mathbf{x}^*)$. Al despejar, obtenemos directamente la condición de estacionariedad de KKT.

Condiciones suficientes de KKT: Del óptimo local al global

Las condiciones necesarias de KKT identifican candidatos a óptimos locales. Sin embargo, cuando el problema presenta ciertas propiedades de convexidad, un punto KKT con $u_i \geqslant 0$ pasa a ser, de forma garantizada, el mínimo global.

Para que estas condiciones necesarias se conviertan en suficientes, se requiere que en el punto factible $\mathbf{x}^*$:

La función objetivo $f(\mathbf{x})$ sea pseudoconvexa: Asegura que no existan falsos mínimos locales. Cualquier función convexa y diferenciable cumple esta propiedad.
Las restricciones activas ($g_i(\mathbf{x}^*) = 0$) sean cuasiconvexas: Garantiza que la región factible no presente cavidades ni formas irregulares. Cualquier restricción lineal o convexa lo cumple.

Cuando se verifican estas dos propiedades geométricas, no hace falta comparar el candidato con ningún otro punto: todo punto que cumpla las condiciones KKT con $u_i \geqslant 0$ es un mínimo global absoluto.

Ejemplo ilustrativo

Consideremos el siguiente problema de optimización:

\[\begin{aligned} \text{Opt.} \quad & f(x_1, x_2) = x_1^2 + x_2^2 \\ \text{s.a:} \quad & x_1 + x_2 \geqslant 1 \\ & x_1 + x_2^2 \leqslant 1 \end{aligned}\]

La representación gráfica de este problema viene dada por:

Para aplicar las condiciones KKT, expresamos todas las restricciones en la forma $g_i(x_1, x_2) \leqslant 0$:

$g_1(x_1, x_2) = 1 - x_1 - x_2 \leqslant 0$
$g_2(x_1, x_2) = x_1 + x_2^2 - 1 \leqslant 0$

Calculamos los gradientes de la función objetivo y de las restricciones:

\[\nabla f(x_1, x_2) = \begin{pmatrix} 2x_1 \\ 2x_2 \end{pmatrix}, \quad \nabla g_1(x_1, x_2) = \begin{pmatrix} -1 \\ -1 \end{pmatrix}, \quad \nabla g_2(x_1, x_2) = \begin{pmatrix} 1 \\ 2x_2 \end{pmatrix}\]

Construimos la función Lagrangiana $L(\mathbf{x}, \mathbf{u})$:

\[L(\mathbf{x}, \mathbf{u}) = x_1^2 + x_2^2 + u_1(1 - x_1 - x_2) + u_2(x_1 + x_2^2 - 1)\]

Formulamos el sistema de ecuaciones e inequaciones KKT:

Estacionariedad ($\nabla_{\mathbf{x}} L = \mathbf{0}$):
- (G1) $2x_1 - u_1 + u_2 = 0$
- (G2) $2x_2 - u_1 + 2 u_2 x_2 = 0$
Factibilidad Primal:
- (F1) $1 - x_1 - x_2 \leqslant 0$
- (F2) $x_1 + x_2^2 - 1 \leqslant 0$
Holgura Complementaria:
- (O1) $u_1 (1 - x_1 - x_2) = 0$
- (O2) $u_2 (x_1 + x_2^2 - 1) = 0$
Factibilidad Dual (según el tipo de optimización):
- Para Minimizar: $u_1 \geqslant 0, \; u_2 \geqslant 0$
- Para Maximizar: $u_1 \leqslant 0, \; u_2 \leqslant 0$
Independencia Lineal: Los gradientes de las restricciones activas ${\nabla g_i(\mathbf{x}^*)}_{i \in \mathcal{I}}$ deben ser linealmente independientes.

Este sistema de ecuaciones se puede resolver utilizando un árbol binario en el que se considera cada multiplicador igual o distinto de $0$ ($u_i = 0$ o $u_i \neq 0$), obteniendo los siguientes puntos candidatos:

Punto	Rama del árbol	Coordenadas $(x_1, x_2)$	Multiplicadores $(u_1, u_2)$
$A$	$u_1 \neq 0, u_2 \neq 0$	$(0, 1)$	$(-2, -2)$
$B$	$u_1 \neq 0, u_2 = 0$	$\left(\frac{1}{2}, \frac{1}{2}\right)$	$(1, 0)$
$C$	$u_1 = 0, u_2 \neq 0$	$(1, 0)$	$(0, -2)$
$D$	$u_1 = 0, u_2 \neq 0$	$\left(\frac{1}{2}, \frac{1}{\sqrt{2}}\right)$	$(0, -1)$

Nota: La rama $u_1 = 0, u_2 = 0$ conduce al punto $(0,0)$, que queda descartado por ser infactible al no cumplir la primera restricción ($1 - 0 - 0 = 1 \nleqslant 0$).

En lugar de evaluar la función objetivo en todos los candidatos, aplicamos el Teorema de Condiciones Suficientes de KKT analizando la naturaleza de las funciones y los multiplicadores obtenidos:

Para el punto candidato a mínimo $B = \left(\frac{1}{2}, \frac{1}{2}\right)$:

Multiplicadores: $u_1 = 1 \geqslant 0$ y $u_2 = 0$. La única restricción activa es $g_1(x_1, x_2) = 1 - x_1 - x_2 = 0$.
Convexidad de la función objetivo: $f(x_1, x_2) = x_1^2 + x_2^2$ es una función estrictamente convexa (su matriz Hessiana es definida positiva), por lo que es pseudoconvexa.
Convexidad de la restricción activa: $g_1(x_1, x_2) = 1 - x_1 - x_2$ es una función lineal (convexa), por lo que es cuasiconvexa.

Al cumplirse la factibilidad dual ($u_1 \geqslant 0$), la pseudoconvexidad de $f$ y la cuasiconvexidad de $g_1$, el Teorema de Condiciones Suficientes garantiza de forma rigurosa que $B = \left(\frac{1}{2}, \frac{1}{2}\right)$ es un mínimo global con valor $z^* = f(B) = 0.5$, sin necesidad de compararlo con ningún otro punto.

Para los puntos $A = (0, 1)$, $C = (1, 0)$ y $D = \left(\frac{1}{2}, \frac{1}{\sqrt{2}}\right)$, los multiplicadores son no positivos, $u_i \leqslant 0$, lo que los identifica como candidatos a máximos.

Para aplicar las condiciones suficientes de máximo global, requeriríamos que $-f(\mathbf{x})$ fuera pseudoconvexa. Sin embargo, como $f$ es estrictamente convexa, $-f$ es estrictamente cóncava (no pseudoconvexa). Por tanto, las condiciones suficientes de KKT no se pueden aplicar para garantizar máximos globales en este problema. En estos escenarios, la clasificación de los máximos se determina mediante análisis gráfico o inspección del borde de la región factible.

Para confirmar de forma rigurosa la existencia y localización de los máximos globales, recurrimos al Teorema del Valor Extremo de Weierstrass. Puesto que la función objetivo $f(x_1, x_2) = x_1^2 + x_2^2$ es continua y la región factible es compacta (cerrada y acotada en $[0, 1] \times [0, 1]$), Weierstrass garantiza la existencia de al menos un máximo y un mínimo absolutos en dicha región.

Como los candidatos a extremos deben cumplir las condiciones necesarias de KKT, basta con evaluar la función en los puntos candidatos a máximo ($A$, $C$ y $D$):

$f(D) = f\left(\frac{1}{2}, \frac{1}{\sqrt{2}}\right) = \left(\frac{1}{2}\right)^2 + \left(\frac{1}{\sqrt{2}}\right)^2 = \frac{1}{4} + \frac{1}{2} = 0.75$
$f(A) = f(0, 1) = 0^2 + 1^2 = 1$
$f(C) = f(1, 0) = 1^2 + 0^2 = 1$

Por tanto, por el Teorema de Weierstrass, $A = (0, 1)$ y $C = (1, 0)$ son los dos máximos globales del problema con valor óptimo $z^* = 1$.

Conclusiones:

Mínimo Global: El punto $B = \left(\frac{1}{2}, \frac{1}{2}\right)$ es el mínimo global con valor óptimo $z^* = 0.5$.
Máximos Globales: Los puntos $A = (0, 1)$ y $C = (1, 0)$ son los dos máximos globales con valor óptimo $z^* = 1$.

El viaje desde los lemas de Farkas y Gordan, pasando por el rigor estructural de Fritz-John, hasta llegar a la elegancia de las condiciones KKT, es uno de los desarrollos más bellos de la matemática aplicada en el siglo XX. Gracias a este recorrido, hoy podemos resolver desde el control de sistemas mecánicos con límites físicos hasta la optimización de carteras y las Máquinas de Vector Soporte (Support Vector Machines, SVM).