Condiciones KKT
Las condiciones de Karush-Kuhn-Tucker (KKT) generalizan los multiplicadores de Lagrange a problemas con restricciones de desigualdad. Son las condiciones de optimalidad de primer orden fundamentales para la optimización restringida: prácticamente todos los algoritmos de optimización, desde el método Simplex hasta los métodos de punto interior o las máquinas de vectores soporte, están construidos alrededor del cumplimiento de las condiciones KKT.
El problema restringido general
\[\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.a.} \quad g_i(x) \leq 0,\; i=1,\ldots,m \quad h_j(x) = 0,\; j=1,\ldots,p\]
El lagrangiano para este problema es:
\[\mathcal{L}(x, \mu, \lambda) = f(x) + \sum_{i=1}^m \mu_i g_i(x) + \sum_{j=1}^p \lambda_j h_j(x)\]
donde \(\mu_i \geq 0\) son los multiplicadores de las restricciones de desigualdad y \(\lambda_j\) (sin restricción de signo) son los multiplicadores de las restricciones de igualdad.
Las cinco condiciones KKT
En un mínimo local \(x^*\) que satisface alguna cualificación de restricciones, existen multiplicadores \(\mu^* \geq 0\) y \(\lambda^*\) tales que:
1. Estacionariedad: \[\nabla f(x^*) + \sum_{i=1}^m \mu_i^* \nabla g_i(x^*) + \sum_{j=1}^p \lambda_j^* \nabla h_j(x^*) = \mathbf{0}\]
2. Factibilidad primal: \[g_i(x^*) \leq 0 \quad \forall i, \qquad h_j(x^*) = 0 \quad \forall j\]
3. Factibilidad dual: \[\mu_i^* \geq 0 \quad \forall i\]
4. Holgura complementaria: \[\mu_i^* g_i(x^*) = 0 \quad \forall i\]
El papel de cada condición:
- Estacionariedad: el gradiente del lagrangiano es cero. Generaliza la condición de Lagrange \(\nabla f = -\lambda \nabla g\) a las desigualdades.
- Factibilidad primal: la solución es factible. Todas las restricciones se cumplen.
- Factibilidad dual: los multiplicadores de las desigualdades son no negativos. Garantiza que las restricciones de desigualdad activas empujan la solución hacia adentro, no hacia afuera.
- Holgura complementaria: para cada restricción de desigualdad, o bien la restricción está activa (\(g_i(x^*) = 0\), frontera ajustada) o bien el multiplicador es cero (\(\mu_i^* = 0\), restricción inactiva sin papel). Los dos no pueden ser simultáneamente distintos de cero.
Holgura complementaria: la condición clave
La holgura complementaria es la condición KKT más distintiva. Dice que una restricción inactiva (con \(g_i(x^*) < 0\): la solución está estrictamente dentro de la región factible) no tiene efecto sobre el óptimo: \(\mu_i^* = 0\) y la restricción desaparece de la condición de estacionariedad.
Una restricción activa (\(g_i(x^*) = 0\): la solución está en la frontera) puede tener \(\mu_i^* > 0\): la restricción es vinculante y su gradiente aparece en la condición de estacionariedad con peso no nulo.
Izquierda: el mínimo no restringido \((3,2)\) está dentro del disco factible. La restricción es inactiva (\(g(x^*)=3^2+2^2-16 = -7 < 0\)), así que \(\mu^* = 0\) y la restricción no tiene ningún papel. Derecha: el mínimo no restringido \((5,4)\) queda fuera de la región factible. El óptimo restringido es la proyección sobre la frontera del disco, donde la restricción es activa (\(g(x^*)=0\)) y \(\mu^* > 0\).
Ejemplo completo: cuadrático con restricción de desigualdad
Minimizar \(f(x,y) = x^2 + y^2\) sujeto a \(g_1: x + y \geq 2\) (es decir, \(2 - x - y \leq 0\)) y \(g_2: x \geq 0\), \(g_3: y \geq 0\).
En forma estándar (\(g_i \leq 0\)): \(g_1 = 2-x-y\), \(g_2 = -x\), \(g_3 = -y\).
Lagrangiano:
\[\mathcal{L} = x^2 + y^2 + \mu_1(2-x-y) + \mu_2(-x) + \mu_3(-y)\]
Estacionariedad:
\[2x - \mu_1 - \mu_2 = 0 \implies \mu_1 + \mu_2 = 2x\]
\[2y - \mu_1 - \mu_3 = 0 \implies \mu_1 + \mu_3 = 2y\]
Por simetría (\(f\) y la restricción activa \(x+y=2\) son simétricas), probamos \(x^* = y^* = 1\).
Comprobación: \(g_1 = 2-1-1=0\) (activa), \(g_2 = -1 < 0\) (inactiva, \(\mu_2=0\)), \(g_3 = -1 < 0\) (inactiva, \(\mu_3=0\)).
De estacionariedad con \(\mu_2=\mu_3=0\): \(\mu_1 = 2x^* = 2\). Factibilidad dual: \(\mu_1=2 > 0\). Holgura complementaria: \(\mu_1 g_1 = 2 \times 0 = 0\), \(\mu_2 g_2 = 0 \times (-1) = 0\), \(\mu_3 g_3 = 0 \times (-1) = 0\). Todo se cumple.
Solución óptima: \(x^* = y^* = 1\), \(f^* = 2\), \(\mu_1^* = 2\).
El multiplicador \(\mu_1^* = 2\) nos dice: ajustar la restricción de \(x+y \geq 2\) a \(x+y \geq 2+\varepsilon\) aumenta el valor óptimo en aproximadamente \(2\varepsilon\).
Suficiencia: cuándo las KKT implican optimalidad global
Las condiciones KKT son siempre necesarias (bajo alguna cualificación de restricciones). Son suficientes para la optimalidad global cuando:
- \(f\) es convexa.
- Cada \(g_i\) es convexa (así \(g_i(x) \leq 0\) define un conjunto factible convexo).
- Cada \(h_j\) es afín (lineal).
En estas condiciones, cualquier punto KKT es un mínimo global. Esto abarca los casos prácticos más importantes: programación lineal, programación cuadrática con objetivo convexo, optimización de carteras convexa, máquinas de vectores soporte.
Para problemas no convexos, los puntos KKT pueden ser mínimos locales, máximos locales o puntos de silla. Encontrar el mínimo global requiere estructura adicional o métodos de búsqueda global.
Aplicación: máquinas de vectores soporte
Las SVM encuentran el hiperplano de margen máximo que separa dos clases. El problema primal es:
\[\min_{w,b} \frac{1}{2}\|w\|^2 \quad \text{s.a.} \quad y_i(w^T x_i + b) \geq 1 \quad \forall i\]
Las condiciones KKT dan el problema dual: solo los vectores soporte (puntos donde \(\mu_i > 0\), es decir, donde la restricción \(y_i(w^T x_i+b) = 1\) está activa) aparecen en la solución. Los puntos alejados del margen tienen \(\mu_i = 0\) por holgura complementaria y son irrelevantes. Esta dispersidad es una consecuencia directa de las KKT.
⚠️ Las condiciones KKT requieren cualificación de restricciones
La cualificación de restricciones más común es la LICQ (Independencia Lineal): los gradientes de las restricciones activas en \(x^*\) deben ser linealmente independientes. Si la LICQ falla, los multiplicadores KKT pueden no existir o no ser únicos.
Situaciones habituales donde puede fallar la CQ:
- Dos restricciones de desigualdad son tangentes entre sí en el óptimo.
- Una restricción tiene gradiente nulo en el óptimo.
- Demasiadas restricciones activas (más de \(n\) restricciones activas en \(\mathbb{R}^n\)).
En la práctica, el fallo de la CQ es raro en problemas bien planteados. Si se sospecha, verificar que los gradientes de las restricciones activas son linealmente independientes en el candidato a óptimo.
💡 Verificar las condiciones KKT en la práctica
Dado un punto candidato \(x^*\), verificar KKT manualmente:
- Comprobar factibilidad primal: todos los \(g_i(x^*) \leq 0\) y \(h_j(x^*) = 0\).
- Calcular \(\nabla f(x^*)\) y \(\nabla g_i(x^*)\) para las restricciones activas.
- Resolver el sistema lineal para \(\mu_i^*\) de la condición de estacionariedad.
- Comprobar factibilidad dual: \(\mu_i^* \geq 0\) para todo \(i\).
- Comprobar holgura complementaria: \(\mu_i^* g_i(x^*) = 0\) para todo \(i\).
En R, verificación KKT numérica tras resolver con nloptr:
library(nloptr)
f <- function(x) x[1]^2 + x[2]^2
grad_f <- function(x) c(2*x[1], 2*x[2])
g_ineq <- function(x) c(2 - x[1] - x[2], -x[1], -x[2])
res <- nloptr(x0=c(0.5, 0.5), eval_f=f, eval_grad_f=grad_f,
eval_g_ineq=g_ineq,
opts=list(algorithm="NLOPT_LD_SLSQP", xtol_rel=1e-8))
res$solution # c(1, 1)
