Optimización con Kuhn-Tucker

Federico Castello Rojo

Facultad de Ciencias Económicas (UNC)

Economı́a Matemática

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 1 / 23

Optimización con restricciones de desigualdad

Comencemos con un ejemplo:




opt. f (x, y ) = x 2 + 3y 2

st. x ≥0


 y ≥0

 x +y ≥1

Vamos a proceder primero de manera “heurı́stica” para luego derivar las

condiciones de primer orden de KKT.

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 2 / 23

Gráfico del dominio
y

x =0

x
+
y
=
1

x
y =0

Caracterı́sticas topológicas: Dominio cerrado, no acotado y convexo.

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 3 / 23

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 4 / 23
Análisis de casos. Interior.

x > 0, y > 0, x + y > 1

CPO:

/ D◦
∇f (x, y ) = (2x, 6y ) = (0, 0) ⇔ (x, y ) = (0, 0) ∈

Por lo tanto, no hay puntos crı́ticos en D ◦ .

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 5 / 23

Análisis de casos. Borde.
1) x = 0, y > 0, x + y > 1

Formamos el Lagrangiano:

L(x, y , λ) = x 2 + 3y 2 − λ[x − 0]

Chequeamos la condición de regularidad:

∇x = (1, 0) ̸= (0, 0) → Se cumple.

CPO:

Lx = 0 ⇔ 2x − λ = 0
Ly = 0 ⇔ 6y = 0
Lλ = 0 ⇔ x = 0

(x, y , λ) = (0, 0, 0) ̸∈ este pedazo de borde.

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 6 / 23
Análisis de casos. Borde.
2) x > 0, y = 0, x + y > 0

Formamos el Lagrangiano:

L(x, y , λ) = x 2 + 3y 2 − λ[y − 0]

Chequeamos la condición de regularidad:

∇y = (0, 1) ̸= (0, 0) → Se cumple.

CPO:

Lx = 0 ⇔ 2x = 0
Ly = 0 ⇔ 6y − λ = 0
Lλ = 0 ⇔ y = 0

(x, y , λ) = (0, 0, 0) ̸∈ este pedazo de borde.

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 7 / 23
Análisis de casos. Borde.
3) x > 0, y > 0, x + y = 0

Formamos el Lagrangiano:

L(x, y , λ) = x 2 + 3y 2 − λ[x + y − 1]

Chequeamos la condición de regularidad:

∇g (x, y ) = (1, 1) ̸= (0, 0) → Se cumple.

CPO:

Lx = 2x − λ = 0 ⇔ 2x = λ
Ly = 6y − λ = 0 ⇔ 6y = λ
Lλ = x + y − 1 = 0 ⇔ x + y = 1

(x, y , λ) = (3/4, 1/4, 3/2) ∈ este pedazo de borde.

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 8 / 23
Análisis de casos. Borde.
Hay un punto crı́tico en x + y = 1. ¿Qué es? Calculemos la CSO:

Lxx =2, Lyy = 6, Lxy = 0

gx = 1, gy = 1

Formamos el Hessiano orlado:

       
0 gx gy 0 1 1 0 1 1 0 1 1
 gx Lxx Lxy  → 1 2 0 → 1 0 −2 → 1 0 0
gy Lxy Lyy 1 0 6 1 0 6 1 0 8

Aw = 8 > 0 → Definida positiva → Min. local

Recordemos que:

∇f = |{z}
λ ∇g
>0

Por lo tanto, ambos gradientes apuntan en la misma dirección.

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 9 / 23
Análisis de casos. Borde.
4) (1, 0) → x > 0, y = 0, x + y = 1

Chequeamos la condición de regularidad:


∇y = (0, 1)
linealmente independientes.
∇g = (1, 1)

Si son linealmente independientes, entonces forman una base de R2 . Por lo

tanto, cualquier vector se puede expresar como una  combinación lineal de
ellos. En particular el vector ∇f (1, 0) = (2x, 6y ) = (2, 0):

(1,0)

λ1 (0, 1) + λ2 (1, 1) = (2, 0)


λ2 = 2
λ1 = −2, λ2 = 2 → silla!
λ1 + λ2 = 0

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 10 / 23

Análisis de casos. Borde.

x =0

x
+
y (0, 1) (1, 1)
=
1 cono
mı́n.

cono
cono
silla
(2, 0)
silla
x
y =0
cono
máx.

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 11 / 23

Análisis de casos. Borde.
5) (0, 1) → x = 0, y > 0, x + y = 1

Chequeamos la condición de regularidad:


∇x = (1, 0)
linealmente independientes.
∇g = (1, 1)

Si son linealmente independientes, entonces forman una base de R2 . Por lo

tanto, cualquier vector se puede expresar como una  combinación lineal de
ellos. En particular el vector ∇f (0, 1) = (2x, 6y ) = (0, 6):

(0,1)

λ1 (1, 0) + λ2 (1, 1) = (0, 6)


λ2 = 6
λ1 = −6, λ2 = 6 → silla!
λ1 + λ2 = 0

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 12 / 23

Análisis de casos. Borde.
y
(0, 6)

(1, 1)
cono x =0
silla cono
mı́n.
(1, 0)
cono
máx.
cono x
silla +
y
=
1

x
y =0

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 13 / 23

Todos los casos en un único Lagrangiano
Supongamos el siguiente problema de minimización:




mı́n f (x, y ) = x 2 + 3y 2

st. x ≥0


 y ≥0

 x +y ≥1

L(x, y , λ1 , λ2 , λ3 ) = f (x, y ) − λ2 [x − 0] − λ2 [y − 0] − λ3 [x + y − 1]

A las CPO le agregamos las condiciones de holgura complementaria:

λ1 Lλ1 = 0
λ2 Lλ2 = 0
λ3 Lλ3 = 0

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 14 / 23

Condiciones de primer orden

λ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.
Lx = 0, Ly = 0 → Optimizo.
λ1 ≥ 0, λ2 ≥ 0, λ3 ≥ 0 → Estoy en el cono de mı́n.

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 15 / 23

CPO en general


λj Lλj = 0 

Lλj ≤ 0 → orientado para mı́n. 


λj ≥ 0 CPO para mı́n.
λxi = 0




j = 1, . . . , m; i = 1, . . . , n



λj Lλj = 0 

Lλj ≥ 0 → orientado para máx. 


λj ≥ 0 CPO para máx.
λxi = 0




j = 1, . . . , m; i = 1, . . . , n


Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 16 / 23

Condiciones de primer orden KKT
Supongamos el siguiente problema de maximización:
 

máx f (x) 
máx f (x)
 
st. g1 (x) ≤ b1 st. g1 (x) ≤ b1

 


 


 .. 
 ..
. .

 


 

gm (x) ≤ bm gm (x) ≤ bm
 
x1 ≥ 0 −x1 ≤ 0

 


 


 .. 
 ..
. .

 


 

 
xn ≥ 0 −xn ≤ 0
 

L(x, λ1 , . . . , λm , µ1 , . . . , µn ) = f (x) − λ1 [g1 (x) − b1 ] − . . .

−λm [gm (x) − bm ] − µ1 [−x1 − 0] − . . . − µn [−xn − 0]

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 17 / 23

Condiciones de primer orden KKT

Simplificando:

L = f (x) − λ1 [g1 (x) − b1 ] − . . . − λm [gm (x) − bm ] + µ1 x1 + . . . + µn xn

Definimos el “lagrangiano corto” de KKT:

L̄ = f (x) − λ1 [g1 (x) − b1 ] − . . . − λm [gm (x) − bm ]

Por lo tanto:

L = L̄ + µ1 x1 + . . . + µn xn

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 18 / 23

Condiciones de primer orden KKT

Lxi = 0 ⇔ L̄xi + µi = 0 ⇔ −L̄xi = µi ≥ 0 ⇔ L̄xi ≤ 0

λj Lxj = 0 ⇔ λj L̄xj = 0

λj ≥ 0

Lλj = L̄λj ≥ 0

µi Lµi = 0 ⇔ µi xi = 0 ⇔ L̄xi xi = 0
|{z}
−L̄xi

µi ≥ 0 → −µi = L̄xi ≤ 0
Lµi ≥ 0 ⇔ xi ≥ 0

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 19 / 23

Condiciones de primer orden KKT

Teorema de Kuhn-Tucker:
Dado un problema de maximización con m restricciones de desigualdad y n
restricciones de no-negatividad (escritas todas bajo la forma de menor o
igual), las CPO que surgen de formar el Lagrangiano:

L̄ = f (x) − λ1 [g1 (x) − b1 ] − . . . − λm [gm (x) − bm ]

donde: L = L̄ + µ1 x1 + . . . + µn xn
vienen dadas por:

xi L̄xi = 0; xi ≥ 0; L̄xi ≤ 0
λj L̄λj = 0; λj = 0; L̄λj ≥ 0

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 20 / 23

Aplicaciones de KKT
Ejercicio 1
Demostrar, utilizando las condiciones de primer orden de KKT, que bajo el
supuesto de monotonicidad de las preferencias el individuo siempre agotará
toda su renta (esto es, que la restricción presupuestaria se cumplirá
siempre con igualdad).

El problema del consumidor es:




 máx u(x1 , x2 )

st. p1 x1 + p2 x2 ≤ m


 x1 ≥ 0 → −x1 ≤ 0

 x2 ≥ 0 → −x2 ≤ 0

El Lagrangiano de KKT será:

L̄(x1 , x2 , λ) = u(x1 , x2 ) − λ[p1 x1 + p2 x2 − m]

Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 21 / 23

Aplicaciones de KKT
Las condiciones de primer orden:
∂u

− λp1 ≤ 0 

∂x1 L̄xi ≤ 0
∂u
− λp2 ≤ 0 

∂x2
  
∂u
x1 − λp1 = 0


 ∂x1

 xi L̄xi = 0
∂u
x2 − λp2 = 0


∂x2


−p1 x1 − p2 x2 + m ≥ 0 → L̄λj ≥ 0
λ(−p1 x1 − p2 x2 + m) = 0 → λj L̄λj = 0

x1 , x2 ≥ 0 → xi ≥ 0
λ ≥ 0 → λj ≥ 0
Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 22 / 23
Aplicaciones de KKT
Adicionalmente, bajo el supuesto de monotonicidad en x1 y x2 :

∂u
>0 (1)
∂x1
∂u
>0 (2)
∂x2
De las CPO:
∂u
≤ λp1 (3)
∂x1
∂u
≤ λp2 (4)
∂x2
Por las restricciones impuestas en (1) y (2) y dado que p1 , p2 > 0, λ debe
ser distinto de cero. Por tanto, λ > 0 y p1 x1 + p2 x2 = m. La restricción
presupuestaria se cumple con igualdad y el individuo agota toda su renta.
Federico Castello Rojo (FCE-UNC) Optimización con Kuhn-Tucker Economı́a Matemática 23 / 23