Lagrange y condiciones KKT
Optimización no lineal con restricciones: multiplicadores de Lagrange (igualdad), las cuatro condiciones KKT (estacionariedad, factibilidad, holgura complementaria), regularidad/LICQ y su diferencia con la convexidad, atajo de reusar el óptimo irrestricto, precio sombra en NLP y cómo leer un MIP Log de Gurobi. Arquetipo E-C del Examen.
functions
Multiplicadores de Lagrange (solo igualdad)
Optimizar con restricciones de igualdad
Para minf(x) sujeto a g(x)=0, el método de Lagrange convierte el problema restringido en uno sin restricciones armando el Lagrangiano:
L(x,λ)=f(x)+λg(x)
En el óptimo, el gradiente de f es paralelo al de la restricción. Se resuelve el sistema anulando las derivadas del Lagrangiano y exigiendo la restricción:
∇xL=∇f+λ∇g=0,g(x)=0
Con varias igualdades gj(x)=0 hay un multiplicador λj por restricción, y la estacionariedad queda ∇f+∑jλj∇gj=0. Los λj de igualdad no tienen restricción de signo (a diferencia de los μi≥0 de las desigualdades).
La idea geométrica: en el óptimo restringido, ∇f no puede tener componente a lo largo de la superficie factible (si la tuviera, moverse por ella mejoraría f). Por eso ∇f queda alineado con ∇g, que es normal a la superficie.
Por qué funciona
Cargando Quiz...
schema
Las condiciones KKT (igualdad y desigualdad)
Generalizar Lagrange a desigualdades
Las condiciones de Karush-Kuhn-Tucker (KKT) extienden Lagrange a restricciones de desigualdad. Para minf(x) s.a. gi(x)≤0, son las condiciones necesarias de primer orden (y suficientes si el problema es convexo y el punto regular).
Las cuatro condiciones
1. Estacionariedad:
∇f(x)+i∑μi∇gi(x)=0
2. Factibilidad primal: gi(x)≤0 (y las igualdades hj(x)=0).
3. Factibilidad dual: μi≥0.
4. Holgura complementaria:
μigi(x)=0∀i
La holgura complementaria es la clave operativa: si una restricción está inactiva (gi(x)<0, con holgura), entonces su multiplicador μi=0. Si μi>0, la restricción está activa (gi(x)=0).
Holgura complementaria significa μi=0 para una restricción inactiva — cero, no positivo. Es el error típico: una restricción con holgura NO aporta a la estacionariedad. Sirve para "apagar" restricciones y reducir el sistema a resolver.
Inactiva ⟹ μ = 0
Cargando Quiz...
psychology
Regularidad (LICQ): cuándo KKT es válida
KKT solo es necesaria en puntos regulares
Un punto es regular si los gradientes de las restricciones activas son linealmente independientes (el Jacobiano de las activas tiene rango completo). Esta es la LICQ (Linear Independence Constraint Qualification).
KKT son necesarias solo en puntos regulares. Un óptimo en un punto singular (gradientes activos dependientes) puede NO admitir multiplicadores KKT. Ejemplo clásico: maxx1 s.a. x2≤(1−x1)3 tiene óptimo (1,0) singular, sin KKT. Siempre verifica LICQ.
Sin regularidad, KKT falla
Regularidad depende SOLO de las restricciones
La regularidad es una propiedad geométrica de la región factible — no depende de f. Da lo mismo qué función optimices sobre ella. Dos formas de garantizarla en todo punto factible sin calcular el Jacobiano a mano:
- Condición de Slater: todas las gi son convexas y existe un punto que las cumple todas estrictamente (gi(x)<0 ∀i, sin tocar ninguna frontera).
- Restricciones lineales/afines: si todas las restricciones son lineales, el punto es regular automáticamente.
No confundir regularidad con convexidad de f
La convexidad de f entra en un teorema distinto. Para que un punto KKT sea garantizadamente el óptimo global (no solo un candidato) se necesita que todo el problema sea convexo: f convexa y región factible convexa y regularidad. Eso es la suficiencia; la regularidad por sí sola solo da la necesidad.
Resumen: regularidad (propiedad de las restricciones) ⟹ KKT es necesaria. Convexidad del problema completo ⟹ KKT es suficiente (todo punto KKT es óptimo global). Son dos garantías separadas.
Necesaria vs suficiente
Cargando Quiz...