Kuhn - Tucker
1 Introducción
Comencemos con un ejemplo:
Min
f (x, y) = x2 + 3y 2
s.a x + y ≥ 1
x ≥ 0, y ≥ 0
Vamos a proceder primero de manera "heurística"para luego derivar las
condiciones de Kuhn-Tucker. Vamos a suponer durante todo el análisis que
el lector ya sabe resolver problemas de maximización con restricciones de
igualdad. La idea es descomponer al problema con restricciones de desigual-
dad en muchos problemas con restricciones de igualdad y un problema sin
restricciones (es decir, en el interior del dominio). Vamos a ir barriendo caso
por caso, para luego mostrar que el método de Kuhn-Tucker no es más que
un algoritmo que junta todos estos problemas en uno solo.
Empecemos graficando el dominio del problema:
Es un conjunto cerrado (incluye a su borde), no acotado y convexo.
Analicemos caso por caso:
1
Interior: x > 0, y > 0, x + y − 1 > 0
Ninguna restricción está activa. Estamos en presencia de un problema de
optimización sin restricciones. Las condiciones de primer orden entonces son:
∇f (x, y) = (0, 0)
(2x, 6y) = (0, 0) ⇐⇒ (x, y) = (0, 0)
Pero (0, 0) no pertenece al interior del dominio. Por lo tanto, no hay
puntos críticos en el interior.
Borde 1: x = 0, y > 0, x + y − 1 > 0
La única restricción activa es x = 0. El Lagrangiano correspondiente para
este problema es:
L(x, y, λ) = x2 + 3y 2 − λx
Las condiciones de primer orden son:
(x) 2x − λ = 0
(y) 6y = 0
(λ) x = 0
La solución al sistema es (x, y, λ) = (0, 0, 0), que no pertenece a este
pedazo de borde. Por lo tanto, no hay puntos críticos por aquí.
Borde 2: x > 0, y = 0, x + y − 1 > 0
La única restricción activa es y = 0. El Lagrangiano correspondiente para
este problema es:
L(x, y, λ) = x2 + 3y 2 − λy
Las condiciones de primer orden son:
(x) 2x = 0
(y) 6y − λ = 0
(λ) y = 0
La solución al sistema es (x, y, λ) = (0, 0, 0), que no pertenece a este
pedazo de borde. Por lo tanto, no hay puntos críticos por aquí.
2
Borde 3: x > 0, y > 0, x + y − 1 = 0
La única restricción activa es x+y −1 = 0. El Lagrangiano correspondiente
para este problema es:
L(x, y, λ) = x2 + 3y 2 − λ(x + y − 1)
Las condiciones de primer orden son:
(x) 2x − λ = 0
(y) 6y − λ = 0
(λ) x + y = 0
La solución al sistema es (x, y, λ) = (3/4, 1/4, 3/2), que sí pertenece a este
pedazo de borde. Además λ > 0, por lo que tenemos un candidato a mínimo.*
Punto “interesante” 1: (x, y) = (1, 0)
Acá tenemos x > 0, y = 0, x + y − 1 = 0.
Hay dos restricciones activas: g1 = y = 0 y g2 = x + y − 1 = 0. Acá
podríamos resolver un Lagrangiano, pero no hace falta. Podemos probar que
los gradientes de las restricciones activas son linealmente independientes:
∇g1 (x, y) = (0, 1)
∇g2 (x, y) = (1, 1)
Entonces forman una base de R2 . Por lo tanto, cualquier vector de R2 se
puede expresar como una combinación lineal de ellos. En particular,
∇f (1, 0) = (2x, 6y)|(1,0) = (2, 0)
se puede escribir como:
(2, 0) = λ1 (0, 1) + λ2 (1, 1)
donde resulta: λ1 = −2 y λ2 = 2. Los multiplicadores tienen signos
opuestos, por lo que el (1, 0) no puede ser un mín. De hecho, es un punto
*Más adelante explicaremos la importancia de los signos de los multiplicadores de
Lagrange en los problemas de optimización restringida. Pero la idea es que si ( x∗ , y ∗ )
es un mín., entonces ∇f (x∗ , y ∗ ) no puede apuntar hacia afuera del conjunto restricción
porque, de hacerlo, podríamos alejarnos de la restricción y encontrar un valor menor
para f . Esto es porque el gradiente de f apunta en su dirección de máximo crecimiento.
Como la restricción está escrita en términos de g(x, y) > c (con mayor o igual), entonces
∇g (x∗ , y ∗ ) también apunta hacia adentro del conjunto restricción. De esta manera, λ > 0
3
silla. Gráficamente, esto se ve así:
Punto “interesante” 2: (x, y) = (0, 1)
Acá tenemos x = 0, y > 0, x + y − 1 = 0.
Hay dos restricciones activas: g1 = x = 0 y g2 = x + y − 1 = 0. De nuevo,
acá podríamos resolver un Lagrangiano, pero no hace falta. Los gradientes de
las restricciones activas son linealmente independientes:
∇g1 (x, y) = (1, 0)
∇g2 (x, y) = (1, 1)
Entonces forman una base de R2 . Por lo tanto, cualquier vector de R2 se
puede expresar como una combinación lineal de ellos. En particular,
∇f (0, 1) = (2x, 6y)|(0,1) = (0, 6)
se puede escribir como:
(0, 6) = λ1 (1, 0) + λ2 (1, 1)
porque en un problema de maximización con restricciones de igualdad se cumple que
∇f (x∗ , y ∗ ) = λ∇g (x∗ , y ∗ ) y ambos gradientes deben apuntar en la misma dirección.
4
donde resulta: λ1 = −6 y λ2 = 6. Los multiplicadores tienen signos
opuestos, por lo que el (0, 1) no puede ser un máx. De hecho, es un punto
silla. Gráficamente, esto se ve así:
2 Todos los casos en un único Lagrangiano:
Supongamos el siguiente problema de minimización:
Min f (x, y)
s.a g(x, y) ≥ c
x ≥ 0, y ≥ 0
Notemos que todas las restricciones están escritas con mayor o igual.
Siempre nos conviene escribir a los problemas de minimización de esta forma.
Así, el gradiente de las restricciones apuntará hacia adentro de la restricción,
que es hacia la dirección donde apunta el gradiente de la función objetivo en
un problema de minimización, y los multiplicadores de Lagrange nos quedarán
positivos en caso de existir un mínimo. El Lagrangiano para este problema es:
L (x, y, λ1 , λ2 , λ3 ) = f (x, y) − λ1 (g1 − c) − λ2 g2 − λ3 g3
5
Nota: Es muy importante mantener la consistencia con los signos. Muchos
libros de texto escriben el Lagrangiano de la siguiente manera:
L (x, y, λ1 , λ2 , λ3 ) = f (x, y) + λ1 (g1 − c) + λ2 g2 + λ3 g3
Es decir, con un signo + adelante de los multiplicadores. Ahí debemos
tener cuidado porque estaríamos invirtiendo todo el orden de los signos con el
que estuvimos trabajando recién. De hecho, para un mín. los multiplicadores
deberán ser negativos si escribimos todo el problema con mayor o igual y
luego decidimos ponerle un + al Lagrangiano. Por ello, una regla práctica es
la siguiente:
Usar un signo - (menos) delante de los multiplicadores y :
Escribir los problemas de minimización con restricciones de mayor o
igual, g(x, y) ≥ c.
Escribir los problemas de maximización con restricciones de menor o
igual, g(x, y) ≤ c.
A las condiciones de primer orden del problema con restricciones de
igualdad la agregamos las condiciones de holgura complementaria (slackness):
λ 1 · L λ1 = 0
λ 2 · L λ2 = 0
λ 3 · L λ3 = 0
De esta forma, el sistema de ecuaciones que describe las condiciones
necesarias para un mín. son:
λ1 Lλ1 = 0, λ2 Lλ2 = 0, λ3 Lλ3 = 0 −→ me paseo por todos los casos
Lλ1 ≤ 0, Lλ2 ≤ 0, Lλ3 ≤ 0 −→ no me salgo del dominio
Lx1 = 0, Lx2 = 0 −→ optimizo
λ1 ≥ 0, λ2 ≥ 0, λ3 ≥ 0 −→ estoy en el cono de mín.
3 Condiciones de primer orden en general:
Supongamos un problema con i = 1, . . . , n variables de elección y j =
1, . . . , m restricciones de desigualdad.
6
1. CPO para mín.
λj Lλj =0
L λj ≤0
L xi =0
λj ≥0
2. CPO para máx.
λj Lλj =0
L λj ≥0
L xi =0
λj ≥0
Ejemplo: Preferencias cuasi lineales
Supongamos que hay dos bienes, x e y, cuyas cantidades deben ser no
negativas, y cuyos precios son respectivamente px y py (ambos positivos).
Consideremos un consumidor con un ingreso de I y una función de utilidad
cuasi lineal de la forma:
u(x, y) = y + α ln(x)
donde a es una constante positiva. Encontremos las demandas óptimas de
x e y usando el teorema de Kuhn-Tucker.
El problema del consumidor es el siguiente:
máx
y + α ln(x)
s.a px x + py y = I
x ≥ 0, y ≥ 0
El Lagrangiano correspondiente es:
L = y + α ln(x) − λ (px x + py y − I) − µ1 (−x) − µ2 (−y)
7
Condiciones de primer orden:
1 − λpy + µ2 =0 (3.1)
α
− λpx + µ1 =0 (3.2)
x
µ1 x = µ2 y =0 (3.3)
µ1 , µ2 ≥0 (3.4)
x ≥ 0, y ≥0 (3.5)
px x + p y y =I (3.6)
Como tenemos dos opciones para los multiplicadores ( µ = 0 ó µ ̸= 0 ) y
dos multiplicadores, la cantidad de casos que debemos chequear es
( #opciones )# multiplicadores = 22 = 4
µ1 ̸= 0, µ2 ̸= 0 : Por (3.3) x = 0, y = 0. Se viola (3.6). El agente no
consume cero de ambos bienes.
µ1 ̸= 0, µ2 = 0 : Por (3.3) x = 0. Entonces por (3.1) λ = 1/py . Usando
esto en (3.2):
α
px /py = µ1 + →∞ Absurdo!
x
|{z}
→∞
El agente no consume cero del bien lineal.
µ1 = 0, µ2 ̸= 0 : Por (3.3) y = 0. Entonces por (3.2) α/x = λpx . Por
(3.6) x = I/px .
Juntando estos dos resultados tenemos que λ = α/I. En (3.1):
α
1− py + µ2 = 0
I |{z}
≥0
α
1 − py ≤ 0
I
α
1 ≤ py
I
I ≤ αpy
8
Esta es una condición sobre los parámetros, que se puede cumplir o no. Si
se cumple, entonces el agente consume cero unidades del bien no lineal.
µ1 = 0, µ2 = 0 : Este es el caso en el que anda todo bien y el agente
consume cantidades positivas de ambos bienes. De (3.1) y (3.2):
1
1 − λpy = 0 =⇒ λ =
py
α α
= 0 =⇒ λ =
x xpx
Entonces:
1 α
=
py xpx
αpy = xpx
py
x=α
px
Reemplazando en (3.6):
!
py
px α + py y = I
px
I
α+y =
py
I I
y= − α |{z}
≥ 0 ⇐⇒ ≥α
py py
(3,5)
⇐⇒ I ≥ αpy
Entonces la solución es:
α py , I −α si I ≥ αpy
(x∗ , y ∗ ) = px py
I ,0 si I ≤ αpy
px