KKT y Dualidad: distintos caminos matemáticos hacia el mismo destino

Imagen de Lance Grandahl extraída de Unsplash

En matemáticas y, en particular, en Investigación Operativa, suele decirse que todos los caminos conducen a Roma. La belleza de la optimización matemática radica en que marcos teóricos desarrollados desde perspectivas distintas convergen de manera exacta hacia los mismos resultados fundamentales.

Vamos a explorar esta convergencia comparando dos herramientas que son pilares de la optimización:

La Teoría de la Dualidad en optimización lineal.
Las Condiciones de Karush-Kuhn-Tucker (KKT), fundamentales en optimización no lineal.

KKT en optimización lineal

A continuación, se muestra formalmente cómo el análisis de Karush-Kuhn-Tucker aplicado a un problema general de Optimización Lineal Continua ($P$) se relaciona intrínsecamente con sus soluciones y con las de su problema dual ($D$).

Consideremos el problema primal $P$ en forma canónica de minimización:

\[P = \begin{cases} \min & z = \mathbf{c}^\intercal \mathbf{x} \\ \text{s.a:} & \mathbf{A}\mathbf{x} \geqslant \mathbf{b} \\ & \mathbf{x} \geqslant \mathbf{0} \end{cases}\]

y su correspondiente problema dual $D$:

\[D = \begin{cases} \max & w = \mathbf{b}^\intercal \mathbf{u} \\ \text{s.a:} & \mathbf{A}^\intercal \mathbf{u} \leqslant \mathbf{c} \\ & \mathbf{u} \geqslant \mathbf{0} \end{cases}\]

Dado el problema $P$ con $n$ variables y $m$ restricciones, si se aborda analíticamente desde el marco general de la Optimización No Lineal con restricciones de desigualdad del tipo $g(\mathbf{x}) \leqslant 0$, reescribimos las restricciones como:

$f(\mathbf{x}) = \mathbf{c}^\intercal \mathbf{x}$
$g_i(\mathbf{x}) = b_i - \mathbf{a}_i^\intercal \mathbf{x} \leqslant 0 \quad \forall i = 1,\ldots,m$
$g_{m+j}(\mathbf{x}) = -x_j \leqslant 0 \quad \forall j = 1,\ldots,n$

donde $\mathbf{a}_i^\intercal$ denota la $i$-ésima fila de la matriz de coeficientes $\mathbf{A}$.

Al haber $m+n$ restricciones de desigualdad en total, asignamos un multiplicador de Lagrange a cada una. El vector total de multiplicadores tiene dimensión $m+n$.

La función Lagrangiana se construye de la siguiente forma:

\[L(\mathbf{x},\mathbf{u}) = \sum_{j=1}^n c_j x_j + \sum_{i=1}^m u_i(b_i - \mathbf{a}_i^\intercal \mathbf{x}) + \sum_{j=1}^n u_{m+j}(-x_j)\]

La determinación de los puntos KKT exige la verificación simultánea de cuatro condiciones fundamentales:

Condición de Estacionariedad (Gradiente):
\[\frac{\partial L}{\partial x_j} = 0 \quad \forall j = 1,\ldots,n \iff c_j - \sum_{i=1}^m u_i a_{ij} - u_{m+j} = 0 \quad \forall j = 1,\ldots,n\]
Condición de Factibilidad Primal:
\[\mathbf{A}\mathbf{x} \geqslant \mathbf{b}, \qquad \mathbf{x} \geqslant \mathbf{0}\]
Condición de Holgura Complementaria (Ortogonalidad):
\[\begin{align*} u_i(b_i - \mathbf{a}_i^\intercal \mathbf{x}) &= 0 \quad \forall i=1,\ldots,m \\ u_{m+j} x_j &= 0 \quad \forall j=1,\ldots,n \end{align*}\]
Condición de Factibilidad Dual (No Negatividad):
\[u_k \geqslant 0 \quad \forall k=1,\ldots,m+n\]

Interpretación teórica

Las condiciones de estacionariedad y factibilidad dual nos permiten reinterpretar el subvector de los primeros $m$ multiplicadores:

\[\mathbf{u}_{dual}^\intercal = (u_1,\ldots,u_m)\]

como una solución factible del problema dual $D$. En efecto, al despejar las ecuaciones de estacionariedad obtenemos $\sum_{i=1}^m u_i a_{ij} \leqslant c_j$, lo que equivale a la condición matricial $\mathbf{A}^\intercal \mathbf{u}_{dual} \leqslant \mathbf{c}$. En esta relación, los multiplicadores adicionales $u_{m+j}$ ($j=1,\ldots,n$) actúan exactamente como las variables de holgura de las restricciones duales.

Por su parte, la condición de ortogonalidad refleja directamente el Teorema de Holgura Complementaria. En consecuencia, todo punto KKT óptimo especifica de forma simultánea la solución óptima para el problema primal $P$ y para su dual $D$.

Aplicación práctica

Para ver esta equivalencia en acción con números reales, resolveremos un problema práctico mediante ambos caminos.

El problema primal

Considérese el siguiente problema de optimización lineal en su forma primal:

\[\begin{align*} \max \quad & z = 3x_1 + 2x_2 \\ \text{s.a:} \quad & x_1 + 2x_2 \leqslant 6 \\ & 2x_1 + x_2 \leqslant 8 \\ & x_1, x_2 \geqslant 0 \end{align*}\]

Resolviendo geométricamente o mediante el algoritmo Símplex, obtenemos la solución óptima primal:

\[\mathbf{x}^* = \left(10/3, 4/3\right)^\intercal, \quad z^* = 38/3 \approx 12,67\]

Camino 1: La teoría de la dualidad

Por el Teorema Fuerte de la Dualidad, asociamos una variable dual $u_1$ a la primera restricción y $u_2$ a la segunda para construir el problema dual de minimización:

\[\begin{align*} \min \quad & w = 6u_1 + 8u_2 \\ \text{s.a:} \quad & u_1 + 2u_2 \geqslant 3 \\ & 2u_1 + u_2 \geqslant 2 \\ & u_1, u_2 \geqslant 0 \end{align*}\]

Como las variables primales son estrictamente positivas en el óptimo ($x_1^* = 10/3$ y $x_2^* = 4/3$), las condiciones de holgura complementaria imponen que ambas restricciones duales se cumplan como igualdades:

$u_1 + 2u_2 = 3$
$2u_1 + u_2 = 2$

Resolviendo este sistema de ecuaciones lineales resulta:

\[\mathbf{u}^* = (1/3, 4/3)^\intercal \quad w^* = 38/3\]

Efectivamente, se cumple la igualdad del valor óptimo: $z^* = w^* = 38/3$.

Camino 2: Las Condiciones de Karush-Kuhn-Tucker (KKT)

Para aplicar KKT, pasamos el problema a la forma estándar de minimización ($f(\mathbf{x}) = -z$ y restricciones $g_i(\mathbf{x}) \leqslant 0$):

\[\begin{align*} \min \quad & f(x_1, x_2) = -3x_1 - 2x_2 \\ \text{s.a:} \quad & g_1(x_1, x_2) = x_1 + 2x_2 - 6 \leqslant 0 \\ & g_2(x_1, x_2) = 2x_1 + x_2 - 8 \leqslant 0 \\ & g_3(x_1, x_2) = -x_1 \leqslant 0 \\ & g_4(x_1, x_2) = -x_2 \leqslant 0 \end{align*}\]

Definimos la función Lagrangiana asignando multiplicadores $u_1, u_2, u_3, u_4 \geqslant 0$:

\[L(\mathbf{x}, \mathbf{u}) = -3x_1 - 2x_2 + u_1(x_1 + 2x_2 - 6) + u_2(2x_1 + x_2 - 8) - u_3 x_1 - u_4 x_2\]

Las condiciones KKT quedan formuladas de la siguiente manera:

Estacionariedad ($\nabla_{\mathbf{x}} L = \mathbf{0}$):

$\frac{\partial L}{\partial x_1} = -3 + u_1 + 2u_2 - u_3 = 0 \implies u_1 + 2u_2 - u_3 = 3$ $\frac{\partial L}{\partial x_2} = -2 + 2u_1 + u_2 - u_4 = 0 \implies 2u_1 + u_2 - u_4 = 2$
Factibilidad Primal:
\[x_1 + 2x_2 \leqslant 6, \quad 2x_1 + x_2 \leqslant 8, \quad x_1 \geqslant 0, \quad x_2 \geqslant 0\]
Holgura Complementaria:
\[\begin{align*} u_1 (x_1 + 2x_2 - 6) &= 0 \\ u_2 (2x_1 + x_2 - 8) &= 0 \\ u_3 x_1 &= 0 \\ u_4 x_2 &= 0 \end{align*}\]
Factibilidad Dual:
\[u_1 \geqslant 0, \quad u_2 \geqslant 0, \quad u_3 \geqslant 0, \quad u_4 \geqslant 0\]

Evaluamos el punto óptimo primal conocido $\mathbf{x}^* = (10/3, 4/3)^\intercal$:

Como $x_1^* > 0$ y $x_2^* > 0$, las ecuaciones de holgura complementaria $u_3 x_1 = 0$ y $u_4 x_2 = 0$ obligan a que $u_3^* = 0$ y $u_4^* = 0$.
Sustituyendo $u_3 = 0$ y $u_4 = 0$ en las condiciones de estacionariedad, obtenemos:
- $u_1 + 2u_2 = 3$
- $2u_1 + u_2 = 2$

El sistema es idéntico al obtenido mediante la teoría de la dualidad, arrojando $u_1^* = 1/3$ y $u_2^* = 4/3$. Ambos multiplicadores son no negativos, por lo que se verifica la factibilidad dual.

Conclusión

La equivalencia entre ambos enfoques es absoluta:

Las ecuaciones de estacionariedad de KKT equivalen a exigir que las restricciones duales se cumplan como igualdades cuando las variables primales son estrictamente positivas.
Los multiplicadores $u_3$ y $u_4$ del enfoque KKT asumen exactamente el papel de las variables de holgura duales.
La factibilidad dual de KKT ($u_i \geqslant 0$) garantiza la no negatividad de las variables en el problema dual.

En definitiva, la dualidad y las condiciones de KKT demuestran la elegancia unificada de la Investigación Operativa: independientemente del marco teórico elegido, la estructura matemática subyacente conduce con absoluta precisión hacia la misma verdad óptima.

¿Quieres seguir explorando el mundo de la Investigación Operativa? Descubre más posts sobre el tema aquí.