Multiplicadores de Lagrange y condiciones KKT

Matemática · Lección 18

L2 Derivación Fase F1 Libro MML §7.2 Prereqs Convexidad · Derivada y gradiente

Objetivo

Al terminar esta lección se puede:

  1. Demostrar la condición de Lagrange: en un óptimo sujeto a g=0 los gradientes de f y de g son paralelos, y el factor de proporcionalidad es el multiplicador.
  2. Escribir el lagrangiano y reconocer que sus puntos críticos son el sistema que hay que resolver.
  3. Demostrar que minimizar una forma cuadrática sobre la esfera unitaria es el problema de eigenvalores de la lección 12.
  4. Enunciar las condiciones KKT con su holgura complementaria, y demostrar que en un problema convexo son suficientes para el óptimo global.

De dónde viene

  • Matemática 13: la regla de la cadena y la fórmula D_vf=\nabla f\cdot v, que es lo que obliga al gradiente a ser ortogonal a las direcciones admisibles.
  • Matemática 15: la caracterización de primer orden de la convexidad (Proposición 15.3). La suficiencia de las KKT se demuestra aplicándola dos veces.
  • Matemática 5: el complemento ortogonal. Que \nabla f sea ortogonal a un hiperplano lo obliga a estar en la recta que lo genera.
  • Matemática 12: el criterio espectral y el cociente de Rayleigh, que aquí reaparecen como un caso particular de Lagrange.

Para qué sirve después

  • Estadística 12 y 16: los máximos de verosimilitud con restricciones —probabilidades que suman uno, varianzas no negativas— se plantean así.
  • Machine Learning: las máquinas de vector soporte son un problema convexo con desigualdades, y son las KKT las que hacen aparecer los vectores soporte como las restricciones activas.
  • Inferencia causal: la reponderación con pesos que suman uno y son no negativos es un problema KKT.

Notación

Símbolo Se lee Significado
g(x)=0 ge de equis igual a cero Una restricción de igualdad
g_i(x)\le0 — Una restricción de desigualdad
\lambda lambda El multiplicador asociado a una restricción
\mathcal{L}(x,\lambda) ele de equis y lambda El lagrangiano, f-\lambda g
x^\star equis estrella El óptimo del problema con restricciones
restricción activa — Una desigualdad que en el óptimo se cumple con igualdad

1. Igualdades: los gradientes se alinean

Definición 18.1 (problema con una restricción de igualdad). Dadas f,g diferenciables, el problema es \min_x f(x) \quad\text{sujeto a}\quad g(x)=0. Un punto es factible si cumple la restricción.

Proposición 18.2 (condición de Lagrange). Sea x^\star un mínimo local de f sobre \{g=0\}, con f y g diferenciables y \nabla g(x^\star)\ne0. Entonces existe \lambda\in\mathbb{R} tal que \nabla f(x^\star) = \lambda\,\nabla g(x^\star).

Demostración. Sea v cualquier vector con \nabla g(x^\star)\cdot v=0. Como \nabla g(x^\star)\ne0, el teorema de la función implícita —que se da por conocido— garantiza que existe una curva diferenciable \gamma:(-\varepsilon,\varepsilon)\to\{g=0\} con \gamma(0)=x^\star y \gamma'(0)=v: las direcciones ortogonales al gradiente de la restricción son exactamente las que se pueden recorrer sin salirse de ella.

La función de una variable t\mapsto f(\gamma(t)) tiene un mínimo local en t=0, porque todos los \gamma(t) son factibles y x^\star es mínimo entre los factibles. Por la Proposición 14.7 aplicada en dimensión uno, su derivada se anula ahí; y por la regla de la cadena (Proposición 13.3) junto con la Proposición 13.8, 0 = \frac{d}{dt}f(\gamma(t))\Big|_{t=0} = \nabla f(x^\star)\cdot\gamma'(0) = \nabla f(x^\star)\cdot v. Esto vale para todo v ortogonal a \nabla g(x^\star). Es decir, \nabla f(x^\star) es ortogonal a todo el hiperplano \{v:\nabla g(x^\star)\cdot v=0\}, y por tanto pertenece a su complemento ortogonal (lección 5), que es la recta generada por \nabla g(x^\star). Luego \nabla f(x^\star)=\lambda\nabla g(x^\star) para algún escalar \lambda. ∎

La lectura geométrica es directa: si los gradientes no fueran paralelos, \nabla f tendría una componente a lo largo de la restricción, y moverse en su contra bajaría f sin salirse de ella. Solo cuando no queda ninguna componente tangencial el punto puede ser óptimo.

Definición 18.3 (lagrangiano). El lagrangiano del problema de la Definición 18.1 es \mathcal{L}(x,\lambda) = f(x) - \lambda\,g(x). Anular sus derivadas parciales reproduce a la vez la condición de la Proposición 18.2 y la restricción: \nabla_x\mathcal{L}=\nabla f-\lambda\nabla g=0, \qquad \frac{\partial\mathcal{L}}{\partial\lambda}=-g(x)=0.

El lagrangiano convierte un problema con restricciones en n variables en un problema sin restricciones en n+1: buscar un punto crítico de \mathcal{L}. Y un sistema de n+1 ecuaciones no lineales es exactamente lo que el método de Newton de la lección 17 sabe resolver.

El ángulo entre los dos gradientes se anula exactamente en el punto donde f alcanza su mínimo sobre la recta, y crece al alejarse en cualquiera de los dos sentidos. Eso es la Proposición 18.2 medida sobre cinco puntos de la restricción.

2. Un caso conocido: la esfera y los eigenvalores

Proposición 18.4 (Lagrange sobre la esfera es el problema de eigenvalores). Sea A simétrica y f(z)=z^\top Az. Los puntos críticos del problema \min_z z^\top Az \quad\text{sujeto a}\quad \|z\|^2=1 son exactamente los eigenvectores unitarios de A, y el multiplicador asociado a cada uno es su eigenvalor. Además f(z^\star)=\lambda, así que el mínimo es el menor eigenvalor.

Demostración. Con g(z)=z^\top z-1 se tiene \nabla f(z)=2Az y \nabla g(z)=2z —el primero porque A es simétrica—. La condición de la Proposición 18.2 es 2Az = \lambda\cdot 2z \quad\Longleftrightarrow\quad Az=\lambda z, que es la definición de eigenvector con eigenvalor \lambda (lección 9). La restricción \|z\|=1 los normaliza. Y evaluando la función en uno de ellos, f(z^\star) = z^{\star\top}Az^\star = z^{\star\top}(\lambda z^\star) = \lambda\,\|z^\star\|^2 = \lambda. Como el mínimo existe —la esfera es compacta y f continua— y todos los candidatos son eigenvalores, el mínimo es el menor de ellos. ∎

Ese resultado ya estaba en la Proposición 12.4, apartado (2), demostrado allí con la diagonalización ortogonal. Aquí sale de un principio distinto y más general, y eso es una comprobación cruzada: dos caminos independientes que llegan al mismo sitio.

Newton sobre el sistema de Lagrange encuentra los dos puntos críticos, con multiplicadores 0{,}792893 y 2{,}207107, que son exactamente los eigenvalores de A. Y en cada uno el valor de la función coincide con su multiplicador, como dice la Proposición 18.4.

3. Desigualdades: las condiciones KKT

Definición 18.5 (problema con desigualdades y condiciones KKT). Para el problema \min_x f(x) \quad\text{sujeto a}\quad g_i(x)\le0,\quad i=1,\dots,m, las condiciones de Karush-Kuhn-Tucker en un punto x^\star con multiplicadores \lambda_i^\star son:

  1. estacionariedad: \nabla f(x^\star) + \sum_i\lambda_i^\star\nabla g_i(x^\star)=0;
  2. factibilidad: g_i(x^\star)\le0 para todo i;
  3. no negatividad: \lambda_i^\star\ge0 para todo i;
  4. holgura complementaria: \lambda_i^\star\,g_i(x^\star)=0 para todo i.

La cuarta condición es la que distingue este caso del de igualdades, y dice algo muy concreto: para cada restricción, o está activa —se cumple con igualdad, g_i=0, y entonces su multiplicador puede ser positivo— o está holgada, y entonces su multiplicador es cero y la restricción no interviene en la estacionariedad. Una restricción que no aprieta no influye.

Bajo hipótesis de regularidad sobre las restricciones, las KKT son necesarias en todo mínimo local. Esa parte se enuncia aquí sin demostrar. Lo que sí se demuestra es la recíproca en el caso convexo, que es la que se usa en la práctica para certificar un óptimo.

Proposición 18.6 (en un problema convexo las KKT son suficientes). Sean f y todas las g_i convexas y diferenciables. Si (x^\star,\lambda^\star) cumple las cuatro condiciones de la Definición 18.5, entonces x^\star es un mínimo global del problema.

Demostración. Sea x cualquier punto factible. Por la Proposición 15.3 aplicada a f, f(x) \;\ge\; f(x^\star) + \nabla f(x^\star)\cdot(x-x^\star). Por la estacionariedad, \nabla f(x^\star)=-\sum_i\lambda_i^\star\nabla g_i(x^\star), de donde f(x) \;\ge\; f(x^\star) - \sum_i\lambda_i^\star\,\nabla g_i(x^\star)\cdot(x-x^\star). Aplicando ahora la Proposición 15.3 a cada g_i, que es convexa, \nabla g_i(x^\star)\cdot(x-x^\star) \;\le\; g_i(x)-g_i(x^\star), y como \lambda_i^\star\ge0 multiplicar por él conserva el sentido de la desigualdad, así que al cambiar el signo, -\sum_i\lambda_i^\star\,\nabla g_i(x^\star)\cdot(x-x^\star) \;\ge\; -\sum_i\lambda_i^\star\big[g_i(x)-g_i(x^\star)\big]. Juntando las dos cotas, f(x) \;\ge\; f(x^\star) - \sum_i\lambda_i^\star g_i(x) + \sum_i\lambda_i^\star g_i(x^\star). El último sumando es cero por holgura complementaria. Y en el penúltimo, cada término cumple \lambda_i^\star\ge0 y g_i(x)\le0 porque x es factible, luego -\lambda_i^\star g_i(x)\ge0 y la suma entera es no negativa. Por tanto f(x) \;\ge\; f(x^\star) para todo x factible: x^\star es mínimo global. ∎

Las cuatro condiciones se usan una vez cada una, y la convexidad se usa dos veces. Quitar cualquiera de las piezas rompe la cadena: sin \lambda_i\ge0 la desigualdad se invierte, sin holgura complementaria queda un término de signo desconocido, y sin convexidad la Proposición 15.3 no se puede aplicar —que es lo que muestra el Ejercicio 2—.

La tabla es la holgura complementaria en acción. Mientras \|c\|\le1 el óptimo es c mismo, la restricción está holgada y \lambda=0: la bola no influye. En cuanto \|c\|>1 el óptimo salta al borde, la restricción pasa a estar activa y \lambda crece con lo que haya que empujar. En ningún caso \lambda y la holgura son ambos distintos de cero.

Ejercicios

Ejercicio 1 — Mínimos cuadrados con una restricción lineal

Minimizar \|y-Xb\|^2 sujeto a a^\top b=c. El lagrangiano es cuadrático, así que anular sus derivadas da un sistema lineal de n+1 ecuaciones. Resolverlo y comprobar que restringir nunca mejora el ajuste.

Ejercicio 2 — Sin convexidad las KKT solo señalan candidatos

Comprobar la Proposición 18.6 en un problema convexo, y encontrar un punto que cumple las cuatro condiciones y sin embargo es el peor punto factible cuando el objetivo no es convexo.

En el problema convexo ninguno de los casi cien mil puntos factibles sorteados mejora al punto que cumple las KKT, como garantiza la Proposición 18.6. En el no convexo, el origen cumple las cuatro condiciones con \lambda=0 y los doscientos mil puntos factibles sorteados son mejores que él: sin convexidad, las KKT no certifican nada.

Reto

En proyectos/notebooks/F1-retos.ipynb, sección Mat 18:

  1. Implementar el método de penalización —minimizar f(x)+\rho\,g(x)^2 sin restricciones, con \rho creciente— y comprobar que la solución converge a la de Lagrange. Medir cómo crece el número de condición de la hessiana con \rho, y relacionarlo con la Proposición 16.5 para explicar por qué el método se vuelve lento.
  2. Resolver la proyección sobre el símplex —minimizar \|x-c\|^2 sujeto a \sum x_i=1 y x_i\ge0— escribiendo las KKT a mano y deduciendo el algoritmo de umbral que sale de la holgura complementaria. Comprobarlo contra un solucionador genérico.
  3. Tomar el Ejercicio 1 y añadir la restricción de desigualdad b_i\ge0. Resolverlo iterando sobre qué restricciones están activas, y anotar en 50-Errores/ cuántas combinaciones hay que probar en el peor caso.

Del libro

Mathematics for Machine Learning trata este material en §7.2 Constrained Optimization and Lagrange Multipliers, dentro del capítulo 7 sobre optimización continua. El libro tiene copyright y no es descargable desde el entorno en que se escribió esta página, así que se cita número y título y no se le atribuye ninguna frase.

Preguntas para leer §7.2 con lápiz:

  1. La sección introduce el lagrangiano y el problema dual asociado. Con la Definición 18.3, ¿por qué el lagrangiano evaluado en un punto factible nunca supera a f en ese punto cuando los multiplicadores son no negativos, y qué dice eso sobre el valor del dual frente al del primal?
  2. §7.2 distingue restricciones de igualdad y de desigualdad. Con la holgura complementaria de la Definición 18.5, ¿por qué una igualdad no impone signo al multiplicador y una desigualdad sí?
  3. El capítulo conecta esta sección con §7.3 sobre optimización convexa. Con la Proposición 18.6, ¿qué se gana exactamente al suponer convexidad, y por qué el Ejercicio 2 es un contraejemplo y no un fallo del método?

Para el Cerebro

Nota nueva en 10-Conceptos/lagrange-kkt.md, enlazada a [[convexidad]], [[eigenvalores]] y [[metodo-de-newton]]. Conviene rehacer a mano la demostración de la Proposición 18.6: usa cada una de las cuatro condiciones KKT exactamente una vez y la convexidad dos, y ver dónde entra cada pieza explica por qué ninguna sobra.

¿Qué dice la condición de Lagrange?::En el óptimo con g = 0, ∇f(x*) = λ∇g(x*): los gradientes son paralelos
¿Por qué tienen que ser paralelos?::Si no, ∇f tendría componente tangente a la restricción y moverse en su contra bajaría f
¿Qué es el lagrangiano?::L(x,λ) = f(x) − λg(x); anular sus derivadas da la condición y la restricción a la vez
¿Cuántas ecuaciones son?::n+1 con n+1 incógnitas, y se resuelven con Newton
¿Qué es Lagrange sobre la esfera unitaria?::El problema de eigenvalores: Az = λz, y f(z*) = λ
¿Cuáles son las cuatro condiciones KKT?::Estacionariedad, factibilidad, multiplicadores no negativos, y holgura complementaria
¿Qué dice la holgura complementaria?::λᵢgᵢ(x*) = 0: o la restricción está activa, o su multiplicador es cero
¿Qué es una restricción activa?::Una desigualdad que en el óptimo se cumple con igualdad; solo esas influyen
¿Cuándo son suficientes las KKT?::Cuando f y todas las gᵢ son convexas (Proposición 18.6)
¿Y si no hay convexidad?::Solo son necesarias: el origen cumple las KKT de min −‖x‖² sobre el disco y es el peor punto
¿Qué pasa con λ al aumentar la presión de la restricción?::Crece: en la proyección sobre la bola, λ = ‖c‖ − 1

Fuentes

Lo que esta página demuestra sola. Las Proposiciones 18.2, 18.4 y 18.6 se demuestran aquí a partir de la regla de la cadena de la lección 13, del complemento ortogonal de la 5 y de la caracterización de primer orden de la convexidad de la 15. Se comprueban además numéricamente: que el ángulo entre \nabla f y \nabla g se anula exactamente donde f es mínima sobre la recta, y crece al alejarse en los dos sentidos; que Newton sobre el sistema de Lagrange en la circunferencia devuelve multiplicadores 0{,}792893 y 2{,}207107, que son los eigenvalores de la matriz de la forma cuadrática, y que en cada punto crítico el valor de la función iguala su multiplicador; la holgura complementaria en cinco escalas del objetivo, con \lambda pasando de cero a positivo justo al salir de la bola; el sistema lineal de mínimos cuadrados con restricción, con la restricción cumplida y el ajuste empeorando; y que en el problema convexo ninguno de 99 458 puntos factibles mejora al punto KKT mientras en el no convexo los 200 000 baten al origen. Los dos visuales se contrastaron antes de publicarse contra las fórmulas en todo el rango de sus controles.

Lo que se usa de otras lecciones sin repetir. La regla de la cadena es la Proposición 13.3 y D_vf=\nabla f\cdot v la 13.8. Que un mínimo local de una función de una variable tiene derivada nula es la Proposición 14.7. El complemento ortogonal de un hiperplano es la lección 5. La caracterización de primer orden de la convexidad, usada dos veces en la Proposición 18.6, es la 15.3. Que el mínimo del cociente de Rayleigh sobre la esfera es el menor eigenvalor es la Proposición 12.4, y aquí se reobtiene por otro camino. El método de Newton para sistemas es la lección 17.

Lo que se enuncia sin demostrar. El teorema de la función implícita, del que depende la existencia de la curva \gamma en la Proposición 18.2. La necesidad de las condiciones KKT en un mínimo local: requiere una hipótesis de regularidad sobre las restricciones y un argumento de separación que quedan fuera de esta lección; aquí solo se demuestra la suficiencia en el caso convexo. En la Proposición 18.4 se usa que el mínimo existe apelando a la compacidad de la esfera sin demostrar el teorema correspondiente.

Lo que viene de los libros.

  • Mathematics for Machine Learning (Deisenroth, Faisal & Ong, Cambridge University Press, 2020), §7.2 Constrained Optimization and Lagrange Multipliers — citada por número y título, sin transcribir texto.

Lo que es mío, no del libro. La Proposición 18.4, que presenta el problema de eigenvalores como caso particular de Lagrange y cierra el círculo con la lección 12 por un camino independiente. La demostración de la Proposición 18.6 escrita para que se vea cada condición KKT usarse una sola vez. Y el Ejercicio 2, construido para que el contraejemplo no sea un punto raro sino el peor punto factible del problema, batido por los doscientos mil puntos sorteados.

Índices verificados el 12-09-2026 contra el índice publicado del PDF oficial.