Optimización con restricciones
Por qué no basta el gradiente
Con restricciones, el óptimo puede estar en el borde factible, donde el gradiente de la función objetivo no se anula. Hay que incorporar la restricción a las condiciones de optimalidad.
El lagrangiano
Se forma sumando a la objetivo los términos de restricción multiplicados por nuevas incógnitas, los multiplicadores. Optimizar el lagrangiano unifica objetivo y límites en una sola expresión.
Multiplicador de Lagrange
Cada restricción de igualdad recibe un multiplicador. Su valor en el óptimo indica cuán cara es esa restricción: a cuánto renunciarías si se relajara una unidad.
Condición de estacionariedad
- El gradiente del lagrangiano respecto a las variables se anula.
- El gradiente respecto a los multiplicadores recupera la restricción.
- Resolver el sistema conjunta óptimo y multiplicadores.
De Lagrange a KKT
KKT añade las restricciones de desigualdad. Aparecen condiciones de holgura complementaria: o la restricción está activa, o su multiplicador es cero.
Holgura complementaria
Es la intuición de que solo las restricciones que «aprietan» en el óptimo tienen coste. Una restricción holgada no influye y su multiplicador se anula.
Activas frente a inactivas
Una restricción está activa si se cumple con igualdad en el óptimo; inactiva si queda margen. KKT claramente separa ambos casos y exige no negatividad de los multiplicadores.
Dualidad
Todo problema tiene un dual. En convexos con cierta regularidad, los valores óptimos coinciden: cero hueco dual. Esta simetría da algoritmos y cota de calidad.
Condiciones de cualificación
KKT es necesario bajo ciertas condiciones de calificación de restricciones. Si el borde se comporta mal, un óptimo podría no cumplirlas y hay que andarse con cuidado.
Usos en machine learning
Las máquinas de vectores soporte se resuelven con KKT, y la holgura complementaria explica su espesitud: solo los vectores de soporte, con multiplicador no nulo, importan.
Errores frecuentes
- Buscar solo puntos interiores con gradiente nulo y olvidar el borde, que es donde suele estar el óptimo.
- Olvidar la no negatividad de los multiplicadores de desigualdad y aceptar soluciones sin sentido.
- Aplicar KKT sin verificar las condiciones de calificación: en bordes mal comportados pueden fallar.
Ejemplo resuelto: maximizar con una igualdad
Quieres el máximo de una producción sujetando el coste a exactamente 200 unidades:
- Formas el lagrangiano: objetivo menos multiplicador por la restricción.
- Anulas el gradiente respecto a las variables y respecto al multiplicador.
- La ecuación del multiplicador recupera la restricción: el coste debe ser 200.
- Resuelves el sistema: obtienes óptimo y multiplicador a la vez.
- Interpretas el multiplicador: producción extra que compraría relajar una unidad de coste.
¿Para qué sirve en la realidad?
El precio de sombra de un multiplicador guía decisiones: cuánto vale aflojar un cupo, una capacidad o un presupuesto. En las máquinas de vectores soporte, la holgura complementaria de KKT es lo que deja el modelo en pocos vectores de soporte.
En las condiciones KKT, la holgura complementaria establece que:
El multiplicador de Lagrange puede interpretarse como la mejora marginal del óptimo al relajar su restricción.
KKT
Toca una tarjeta para ver la respuesta.
Ordena la construcción de las condiciones KKT:
Arrastra cada ficha a su categoría (o tócala y luego toca la categoría). También puedes usar el teclado.
Condiciones KKTCondiciones de optimalidad con desigualdades.
Une cada término de la optimización restringida con su definición.
El precio de una restricción
- Optimización con restricciones
- Igualdades
- lagrange
- lagrange
- precio de sombra
- Igualdades
- kkt
- activa o inactiva
- problema dual
En tu óptimo un multiplicador vale cero. ¿Qué te dice sobre la restricción asociada: está apretando o sobra holgura? Razona por holgura complementaria.
Tu texto se guarda sólo en este dispositivo.
Comentarios
Inicia sesión para comentar.
Todavía no hay comentarios. Sé la primera persona en opinar.