deber optimización
TRANSCRIPT
-
7/24/2019 Deber Optimizacin
1/5
Escuela Politecnica Nacional
Optimizacion II
Deber 1
Milton Torres Espana
10 de noviembre de 2015
Ejercicio 1 Pruebe que (LFCQ) implica (CQ).
Solucion:
Supongamos que todas las restriccionesci(x) coni A(x) son lineales, es decir, cumplen LFCQ.
Tenemos que probar que SF D(x, ) = LF D(x, ). Sabemos, por el Lema 2.1, que SF D(x, ) LF D(x, ). As, bastara probar LF D(x, ) SF D(x, ).
Sead LF D(x, ). Por definicion, para todo i Ese tiene dTci(x) = 0 y para todo i I(x)
se verifica que dTci(x) 0. Como las restricciones activas son lineales, existe ai R
n tal queci(x) =ai con ai R
n para todo x . Sea M >0 suficientemente pequeno tal que x +M d ,como es convexo y ci lineal se tiene
ci(x +M d) =ci(x
) +M dci(x)
=ci(x) +M dai,
para i A(x) obtenemos ci(x + M d) = 0 o ci(x
+ M d) 0. Finalmente, definimos dk = dy k =
M
k > 0 para k N tales que dk d y k 0. Es claro que para k N se tiene que
xk = x +kdk . Luego, d SF D(x
, ).
Ejercicio 2 Considere el problema de optimizacion siguiente:
mnxRn
f(x)
sujeto a
ci(x) = 0, i= 1, . . . , me,
ci(x) 0, i= me+ 1, . . . , m ,
(1)
donde f : Rn R es una funcion convexa, ci(x) (i = 1, . . . , me) son funciones lineales y ci(x)(i= me+ 1, . . . , m) son funciones concavas. Sea x
un mnimo local de (1). Probar que x es tambienun mnimo global de (1).
Solucion:
Como f es una funcion convexa bastara probar que el conjunto de punto factibles es convexo.Sean x, y . Para i = 1, 2, . . . , me, ci es lineal, por lo que podemos escribir a cada una de lasrestricciones como
ci(x) =n
k=1
ikxk+i,
1
-
7/24/2019 Deber Optimizacin
2/5
donde x= (x1, x2, . . . , xn), ik Ry i R. Sea t [0, 1],
ci((1 t)x+ty) =n
k=1
ik((1 t)xk+tyk) +i
= (1 t)ci(x) +tci(y)
= 0,
ya que ci(x) = ci(y) = 0. Ahora, para i = me+ 1, . . . , m, tenemos que ci(x) 0 y ci(y) 0. Por laconcavidad de las restricciones,
ci((1 t)x+ty) (1 t)ci(x) +tci(y)
0.
Por lo tanto, (1 t)x+ty . Luego, es convexo.
Ejercicio 3 Considerar el problema de optimizacion siguiente:
mnxR2 f(x) :=x2
1+ 2x2
2
sujeto a
x1+x2 2 = 0.
Encuentre un punto que satisfaga las condiciones KKT y verifique que dicho punto es, en efecto, unasolucion optima del problema. Repita el ejercicio si se cambia la funcion objetivo por x3
1+x3
2.
Solucion:
i) Para f1(x) :=x21
+ 2x22
. Escribimos la funcion Lagrangiana L(x, ) =x21
+ 2x22
(x1+x2 2)y su derivada xL = (2x1 , 4x2 ). Con ello formamos el sistema de condiciones KKT:
2x1 = 04x2 = 0x1+x2 = 2
0
La solucion de este sistema es x1 = 4
3, x2 =
2
3 y = 8
3. Por tanto, el punto x=
4
3, 23
es KKT.
Ahora probemos que x =4
3, 23
es una solucion optima del problema. Para ello, sea x = (a, b)
Figura 1: Curvas de nivel de f1(x) y solucion optima del problema.
2
-
7/24/2019 Deber Optimizacin
3/5
comoxtiene que pertenecer al conjunto de puntos factible, verifica que a = 2b. As, consideremosel problema equivalente unidimensional
mnbR
f(b) := (2 b)2 + 2b2,la solucion de este problema es b = 2
3. Por tanto, a = 4
3. Es una solucion global pues
f
2
3>
0.Luego, x= 43 , 23 es una solucion optima. Esta concuerda con el punto KKT encontrado.ii) Paraf2(x) :=x
31
+ x32
. La funcion Lagrangiana es L(x, ) =x31
+ x32
(x1 + x2 2) y su derivadaes xL = (3x
21
, 3x22
). As, el sistema de condiciones KKT es
3x21
= 03x2
2 = 0
x1+x2 = 2 0
La solucion de este sistema es x1= 1, x2= 1 y = 3. Por tanto, el punto x= (1, 1) es KKT. Sea
Figura 2: Curvas de nivel de f2(x) y solucion optima del problema.
x= (a, b), tenemos el problema unidimensional equivalente
mnbR
f(b) := (2 b)3 +b3.La solucion del problema es b = 1, entonces a = 1. Es una solucion global pues
f (1) > 0. Por
tanto, el punto KKT encontrado es una solucion optima del problema.
Ejercicio 4 Considere el problema de optimizacion siguiente:
mnxR2
x1
sujeto a
x2 x3
1
x31 x2.
Pruebe que este problema no satisface las condiciones KKT.
Solucion:
3
-
7/24/2019 Deber Optimizacin
4/5
Sean x = (x1, x2)T, = (1, 2)
T, f(x) = x1, c1(x) = x31
x2 y c2(x) = x2+ x31
. Definimos ellagrangiano de este problema:
L(x, ) =x1 1(x3
1 x2) 2(x2+x
3
1).
As, xL(x, ) = (1 31x21
32x21
, 1 2).
Por tanto el sistema de condiciones KKT sera
1 31x2
1 32x
2
1= 0 (2a)
1 2= 0 (2b)
x31 x2 0 (2c)
x2+x3
1 0 (2d)
1(x3
1 x2) = 0 (2e)
2(x2+x3
1) = 0 (2f)
1 0 (2g)
2 0 (2h)
De (2b), tenemos que 1 = 2. Luego,
1 31(x2
1+x22) = 0. ()
Tenemos dos casos: si 1 = 2= 0 tenemos una contradiccion con (). Ahora, si 1 = 2= 0 entonceshay una contradiccion entre (2e) y (2f). Por tanto, el problema no tiene puntos que satisfagan lascondiciones KKT.
Ejercicio 5 Considere el problema de optimizacion siguiente:
mnxR2
f(x) := x1+ 3x2+ 32x1+x2+ 6
sujeto a
2x1+x2 12
x1+ 2x2 4
x1, x2 0.
a) Pruebe que las condiciones KKT son suficientes para este problema.
b) Pruebe que cualquier punto en el segmento que une (0, 0) y (6, 0) es una solucion optima del
problema.
Solucion:
a) Sean x= (x1, x2), = (1, 2, 3, 4) y
L(x, ) = x1+ 3x2+ 3
2x1+x2+ 6+ 1(x
3
1 x2) 2(x2+x3
1) 3x1 4x2.
Sea x = (0, 0) una solucion local del problema, tenemos c1(x) = (2, 1), c2(x
) = (1, 2),c3(x
) = (1, 0) y c4(x) = (0, 1). Estos vectores son linealmente independientes, por tanto LICQ
se verifica para x. Luego,
xL(x, ) =
21 2 35
12+ 1+ 22 4
.
4
-
7/24/2019 Deber Optimizacin
5/5
Con ello formamos el siguiente sistema:
21 2 3 = 01+ 22 4 = 0
1 02 03 04 0
41 = 0122 = 0
La solucion del este sistema es =
0, 0, 0, 512
. Por tanto, xL(x
, ) =
00
. Entonces las
condiciones KKT son suficientes para este problema.
b) Sea x = (t, 0) tal que t [0, 6]. Primero verifiquemos que x es un punto factible. Tenemos que2t 12, t 4 y t 0 para todo t [0, 6]. Por tanto, x es un punto factible. Notemos quef(0, 0) = 1
2. Ademas,
f(t, 0) = t+ 32t+ 6
= t+ 32(t+ 3)
= 12
,
para t [0, 6]. Luego, todos los puntos (t, 0) estan en la misma curva de nivel y por el literalanterior todos los puntos (t, 0) con t [0, 6] son soluciones optimas del problema.
5