Pauta Auxiliar N 11 1

Facultad de Ciencias F´ısicas y Matem´
aticas
Universidad de Chile
26 de Junio de 2014

IN3701 - Modelamiento y Optimizaci´
on
Auxiliar 11 - Optimizaci´on No lineal con Restricciones
Profs: V´ıctor Bucarey, Roberto Cominetti.
Aux: Basti´
an Bahamondes, Carlos Bonet, Cristobal Haye, Diego Fuentealba, Hugo Navarrete.

Pregunta 1:
Soluci´
on:
Primero se lleva el problema a la forma est´
andar
x2 (y+ 3)2
+
16
9

(P ) M in F (x, y) =

g1 (x, y) = x2 − y ≤ 0
g2 (x, y) = x2 + (y − 2)2 − 4 ≤ 0
Ahora calculamos los gradientes de f y gi
∇f (x, y) =

2x/16
2(y + 3)/9

2x
−1

∇g1 (x, y) =

∇g2 (x, y) =

2x
2(y − 2)

As´ı, se tiene que las condiciones de KKT son las siguientes:
2x/16
2(y + 3)/9

+ µ1

2x
−1

+ µ2

2x
2(y − 2)

=0

y
µ1 (x2 − y) = 0
µ2 (x2 + (y − 2)2 − 4) = 0
Evaluando en el punto (0,0), nos queda:
µ1 ∗ (0 − 0) = 0

⇒ µ1 ∈ R +

µ2 ∗ (0 + (0 − 2)2 − 4) = 9

⇒ µ 2 ∈ R+

Entonces,
0
6/9

+ µ1

0
−1

+ µ2

0
−4

=0

A primera vista no podemos despejar los valores de los multiplicadores, sin embargo debemos notar que

0
−1

0
son linealmente dependientes, por tanto el punto no es regular. Luego no podemos concluir nada de
−4
este punto con KKT.
y

1

Facultad de Ciencias F´ısicasy Matem´
aticas
Universidad de Chile
26 de Junio de 2014

Figura 1: Gr´afico regi´on factible para (P ).

(P ) M in F (x, y) = (x − 1)2 + (y + 1)2
g1 (x, y) = 15x3 − 5y ≤ 0
Ahora calculamos los gradientes de f y gi
∇f =

2(x − 1)
2(y + 1)

45x2
−5

∇g1 =

As´ı, se tiene que las condiciones de KKT son las siguientes:
2(x − 1)
2(y + 1)

+ µ1

45x2
−5

=0

µ1 (15x3 − 5y) = 0
Evaluando en el punto(0, 0), nos queda:
µ1 (0 − 0) = 0

⇒ µ1 ∈ R +

Entonces,
−2
2

+ µ1

0
−5

=0

De aqu´ı se tiene una contradicci´
on. Dado que −2 = 0. Por esto, no se cumplen las condiciones de KKT. Como
se ve gr´aficamente es l´
ogico que el punto (0, 0) no cumple las condiciones dado que no es ´optimo.

2

Facultad de Ciencias F´ısicas y Matem´
aticas
Universidad de Chile
26 de Junio de 2014

Figura 2: Gr´aficoregi´on factible para (P ).
Pregunta 2:
(i) Las condiciones de KKT son:
• factibilidad primal: µT x ≥ α, x ≥ 0
• factibilidad dual: λ ≥ 0, δ ≥ 0
• holgura complementaria: λ(α − µT x) = 0, δ T x = 0
• ecuaci´on de gradientes: 2Σx − λµ − δ = 0
(ii) Si. Primero vemos que es un problema convexo. Es decir la funci´on objetivo es convexa (Σ es definida
positiva), y las desigualdades son lineales, porende convexas. Adem´as este es un problema que tiene un
punto de Slater, pues uno puede construir un punto x
¯ que satisfaga µT x
¯>αyx
¯ > 0. Problema convexo
que tiene punto de Slater es la condici´
on para garantizar que existe optimo sin gap y que entonces satisface
KKT.
(iii) Suponga que α > 0 y que µT x > α. Por holgura complementaria esto significa que λ = 0, lo que significa
por la ecuaci´on de gradientes que x = 12 Σ−1 δ. Donde Σ−1 es definida positiva pues Σ lo es. De holgura
complementaria nuevamente, tenemos que 0 = δ T x = 21 δ T Σ−1 δ. Como Σ−1 es definida positiva esto
significa que δ = 0 = 12 Σ−1 δ = x. Por lo tanto µT x = 0 que no puede ser > α > 0. Lo que es una
contradicci´on. Y µT x = α con λ ≥ 0.
(iv) Usando las condiciones de KKT, cuando µT x = α > 0, tenemos que 2σi2xi = λµi +δi para todo i = 1, . . . , n.
Vemos primero que λ > 0. Si λ = 0 entonces 0 = δi xi = 2σ1 2 δi2 , lo que implica que δi = 0 y xi = 0 una
i

contradicci´on pues µT x = α > 0. Si µi > 0, entonces xi > 0 y δi = 0. Lo que deja xi = 2σλ2 µi . Similarmente
i
podemos ver que pasa si µi < 0, que significa que δi > 0 y xi = 0. Si µi = 0 nuevamente tenemos tenemos
0 = δi xi = 2σ1 2 δi2 que nosdeja xi = 0. Por lo tanto se tiene
i

xi =

0
λ
µ
2σi2 i

3

si µi ≤ 0
si µi > 0

Facultad de Ciencias F´ısicas y Matem´
aticas
Universidad de Chile
26 de Junio de 2014

Usamos la condici´
on µT x = α para determinar el valor de λ que resulta ser
µ2i
).
σ2
i:µ >0 i

λ = 2α/(

i

(v) La parte anterior nos muestra que solo conviene invertir en activos que tienen µi > 0. Por lo tanto se
debe tener el...