clase04 120407

Vista previa del material en texto

FACULTAD CS. FI´SICAS Y MATEMA´TICAS UNIVERSIDAD DE CHILE
MA57B Optimizacio´n No Lineal. Semestre 2007-1
Profesor: He´ctor Ramı´rez C. Auxiliar: Oscar Peredo.
Clase Auxiliar #4
Ana´lisis de Sensibilidad en Optimizacio´n No Lineal
12 de abril de 2007
1. Sensibilidad en caso de restricciones de igualdad
Recordemos dos teoremas importantes:
Teorema 1.1 (Funcio´n Impl´ıcita). Sea f : Rm+n → Rm funcio´n de x ∈ Rm e y ∈ Rn tal que:
1. f(x, y) = 0
2. f es continua y la matr´ız ∇yf(x, y) es no singular en algu´n abierto que contiene a (x, y)
Entonces existen:
1. Abiertos Sx y Sy que contiene a x e y respectivamente.
2. Una funcio´n continua φ : Sx → Sy tal que y = φ(x) y f(x, φ(x)) = 0 en Sx.
Adema´s si f es continuamente diferenciable para algu´n p > 0, lo mismo se tiene para φ.
Teorema 1.2 (Condiciones de Suficiencia de Segundo Orden en caso de igualdad). Supongamos
que f y h son de clase C2 y sean x∗ ∈ Rn, λ∗ ∈ Rm que satisfacen
∇xL(x∗, λ∗) = 0 ∇yL(x∗, λ∗) = 0 (1)
∇2xxL(x∗, λ∗) � 0 para todo y 6= 0 tal que ∇h(x∗)T y = 0 (2)
Entonces x∗ es un minimo local estricto de f sujeto a h(x) = 0.
Ahora probemos el primer teorema de sensibilidad:
Teorema 1.3 (Sensibilidad en caso de igualdad). Sean x∗ ∈ Rn, λ∗ ∈ Rm minimo local y multiplicador
de Lagrange respectivamente, donde ambos satisfacen las condiciones de suficiencia de segundo orden del
teorema 1.2. Considere la familia de problemas
mı´n{f(x) : x ∈ Rn, h(x) = u} (3)
parametrizada por el vector u ∈ Rm. Entonces existe una bola abierta centrada en u = 0 tal que para todo
u ∈ S existen (x(u), λ(u)) ∈ Rn+m par minimo local y multiplicador de Lagrange de 3. Adema´s x(·) y λ(·)
son continuamente diferenciables en S, x(0) = x∗ y λ(0) = λ∗, y se tiene que ∀u ∈ S
∇up(u) = −λ(u)
con p(u) = f(x(u)) el costo optimal parametrizado por u.
1
Demostracio´n. Trataremos de usar el teorema de la funcio´n impl´ıcita. Consideremos el sistema
∇f(x) +∇h(x)λ = 0, h(x) = u (4)
Tomemos la funcio´n F (u, (x, λ)) =
( ∇f(x) +∇h(x)λ
h(x)− u
)
, que es continua por hipo´tesis del teorema 1.2.
Evaluando en el punto (0, (x∗, λ∗)), se tiene que F (0, (x∗, λ∗)) = 0. Calculemos ∇(x,λ)F (0, (x∗, λ∗)):
J = ∇(x,λ)F (0, (x∗, λ∗)) =
[ ∇2xxL(x∗, λ∗) ∇h(x∗)
∇h(x∗)T 0
]
(5)
Probemos que J es no singular. Si fuera singular, existe un vector (y, z) 6= 0 tal que J · (y, z) = 0, es decir,
∇2xxL(x∗, λ∗)y +∇h(x∗)z = 0 (6)
∇h(x∗)T y = 0 (7)
Premultiplicando 6 por yT y usando 7 se tiene que yT∇2xxL(x∗, λ∗)y = 0, pero por hipo´tesis del teorema
1.2, ∇2xxL(x∗, λ∗) � 0, se tiene y = 0. Usando y = 0 en 6, se tiene ∇h(x∗)z = 0, lo cual implica z = 0 por
independencia lineal de las columnas de ∇h(x∗) (hipo´tesis de 1.2). Esto implica que (y, z) = 0, lo cual es
una contradiccio´n.
Ahora, usando teorema de la funcio´n impl´ıcita, con F (u, (x, λ)), existe una bola abierta S centrada en
u = 0 tal que las funciones x(·) y λ(·) son continuamente diferenciables, x(0) = x∗, λ(0) = λ∗ y adema´s
∇f(x(u)) +∇h(x(u))λ(u) = 0 (8)
h(x(u)) = u (9)
Veamos que el par (x(u), λ(u)) satisfacen las hipo´tesis del teorema 1.2 para u suficientemente cer-
cano a cero. Supongamos que no, es decir, existen sucesiones uk → 0 e yk (sin perdida de generalidad,
suponemos ‖yk‖ = 1, haciendo Nikita Nipone con la norma) que satisfacen ∇h(x(uk))T yk = 0,∀k y
yTk∇2xxL(x(uk), λ(uk))yk ≤ 0,∀k. Llamemos yk a alguna subsucesio´n convergente de yk, con l´ımite y˜. Si se
cumple yTk∇2xxL(x(uk), λ(uk))yk ≤ 0, tomando l´ımite y usando continuidad se tiene y˜T∇2xxL(x(0), λ(0))y˜ ≤
0, lo cual es una contradiccio´n.
Falta probar ∇up(u) = ∇u{f(x(u))} = −λ(u). Multiplicando 8 por ∇x(u) se tiene
∇ux(u)∇xf(x(u)) +∇ux(u)∇xh(x(u))λ(u) = 0 (10)
Derivando 9 con respecto a u se tiene
∇uh(x(u)) = ∇uu
∇ux(u)∇xh(x(u)) = I
Finalmente, derivando f(x(u)) con respecto a u
∇uf(x(u)) = ∇ux(u)∇xf(x(u))
Combinando las dos u´ltimas ecuaciones con 10, se obtiene el resultado ∇up(u) + λ(u) = 0.�
2. Sensibilidad en caso de restricciones de desigualdad
El caso de restricciones de desigualdad se reduce a restricciones de igualdad, despreciando las restric-
ciones no activas de la siguiente manera:
Lema 2.1. Si x∗ es o´ptimo local del problema mı´n{f(x) : h(x) = 0, g(x) ≤ 0, x ∈ Rn} entonces x∗ es
o´ptimo local del problema mı´n{f(x) : h(x) = 0, gj(x) ≤ 0, j ∈ A(x∗)} con A(x∗) = {j : gj(x∗) = 0}
2
Usando este lema, y el teorema 2.1, el teorema de sensibilidad en caso de desigualdades 2.2 se demuestra
de manera ana´loga al teorema 1.3
Teorema 2.1 (Condiciones de Suficiencia de Segundo Orden en caso de desigualdad). Supon-
gamos que f , h y g son de clase C2 y sean x∗ ∈ Rn, λ∗ ∈ Rm, µ∗ ∈ Rr que satisfacen
∇xL(x∗, λ∗, µ∗) = 0, h(x∗) = 0, g(x∗) ≤ 0 (11)
µ∗j > 0, j ∈ A(x∗) µ∗j = 0, j /∈ A(x∗) (12)
∇2xxL(x∗, λ∗, µ∗) � 0 para todo y 6= 0 tal que ∇h(x∗)T y = 0,∇gj(x∗)T y = 0,∀j ∈ A(x∗) (13)
Entonces x∗ es un minimo local estricto de f sujeto a h(x) = 0 y g(x) ≤ 0.
Teorema 2.2 (Sensibilidad en caso de desigualdad). Sean x∗ ∈ Rn, λ∗ ∈ Rm, µ∗ ∈ Rr minimo local
y multiplicadores de Lagrange respectivamente, que satisfacen las condiciones de suficiencia de segundo
orden del teorema 2.1. Considere la familia de problemas
mı´n{f(x) : x ∈ Rn, h(x) = u, g(x) ≤ v} (14)
parametrizada por el vector (u, v) ∈ Rm+r. Entonces existe una bola abierta centrada en (u, v) = (0, 0) tal
que para todo (u, v) ∈ S existen (x(u, v), λ(u, v), µ(u, v)) ∈ Rn+m+r tr´ıo minimo local y multiplicadores de
Lagrange de 14. Adema´s x(·), λ(·) y µ(·) son continuamente diferenciables en S, x(0, 0) = x∗, λ(0, 0) = λ∗
y µ(0, 0) = µ∗, y se tiene que ∀(u, v) ∈ S
∇up(u, v) = −λ(u, v)
∇vp(u, v) = −µ(u, v)
con p(u, v) = f(x(u, v)) el costo optimal parametrizado por (u, v).
3. Aplicacio´n
A partir de los dos teoremas principales de las secciones anteriores, podemos estimar la variacio´n de la
funcio´n objetivo, dada una perturbacio´n del lado derecho en caso de restricciones de igualdad o desigualdad.
Supongamos que el problema mı´n{f(x) : h(x) = 0} con solucio´n x∗, se perturba de la forma h(x) = δ, con
‖δ‖ chico. La solucio´n del problema perturbado sera´ x∗ +∆x, luego, se tiene que
∆costo = f(x∗ +∆x)− f(x∗)
= ∇f(x∗)T∆x+ o(‖∆x‖)
= (−∇h(x∗)λ)T∆x+ o(‖∆x‖)
= −λT∇h(x∗)T∆x+ o(‖∆x‖)
De las restricciones tenemos que
δ = h(x∗ +∆x)− h(x∗)
= ∇h(x∗)T∆x+ o(‖∆x‖)1m
por lo tanto
∆costo = −λT∇h(x∗)T∆x+ o(‖∆x‖)
= −λT (δ − o(‖∆x‖)1m) + o(‖∆x‖)
= −λT δ + o(‖∆x‖)[λT1m + 1]
≈ −λT δ
3
Ahora, supongamos que el problema mı´n{f(x) : h(x) = 0, g(x) ≤ 0} con solucio´n x∗, se perturba de la
forma h(x) = δ, g(x) ≤ γ, con ‖δ‖ y ‖γ‖ chicos. La solucio´n del problema perturbado sera´ x∗ +∆x, luego,
se tiene que
∆costo = f(x∗ +∆x)− f(x∗)
= ∇f(x∗)T∆x+ o(‖∆x‖)
= (−∇h(x∗)λ−∇g(x∗)µ)T∆x+ o(‖∆x‖)
= −λT∇h(x∗)T∆x− µT∇g(x∗)T + o(‖∆x‖)
De las restricciones tenemos que
δ = h(x∗ +∆x)− h(x∗)
= ∇h(x∗)T∆x+ o(‖∆x‖)1m
γ = g(x∗ +∆x)− g(x∗)
= ∇g(x∗)T∆x+ o(‖∆x‖)1r
por lo tanto
∆costo = −λT∇h(x∗)T∆x− µT∇g(x∗)T + o(‖∆x‖)
= −λT (δ − o(‖∆x‖)1m)− µT (γ − o(‖∆x‖)1r) + o(‖∆x‖)
= −λT δ − µTγ + o(‖∆x‖)[λT1m + µT1r + 1]
≈ −λT δ − µTγ
donde µj = 0 para j /∈ A(x∗) y µj > 0 para j ∈ A(x∗).
Esto coincide con el resultado que nos entrega el teorema:
f(x∗ +∆x)− f(x∗) = p(u, v)− p(0, 0)
= ∇up(0, 0)Tu+∇vp(0, 0)T v + o(‖u‖) + o(‖v‖)
= −λ(0, 0)Tu− µ(0, 0)T v + o(‖u‖) + o(‖v‖)
≈ −λ(0, 0)Tu− µ(0, 0)T v
Problema 1. Se sabe que 3 fondos mutuos A, B y C tienen retornos esperados del 10%,10% y 15%. Se
desea invertir en estos 3 fondos, minimizando el riesgo asociado, de tal manera que el retorno esperado
sea de un 12%. El riesgo se calcula como la varianza de la inversio´n, en este caso:
400x2 + 800y2 + 200xy + 1600z2 + 400yz
¿Que ocurre si se desea un retorno del 12.5%?
Solucio´n 1. Definamos las variables x, y, z como el porcentaje de mis recursos que invierto en fondo A,
B y C. El problema se plantea de la forma:mı´n 400x2 + 800y2 + 200xy + 1600z2 + 400yz
s.a x+ y + 1,5z = 1,2
x+ y + z = 1
4
Sin agregar las restricciones de positividad, usando multiplicadores de Lagrange, se tiene que:
L(x, y, z, λ1, λ2) = 400x2 + 800y2 + 200xy + 1600z2 + 400yz + λ1(1− x− y − z) + λ2(1,2− x− y − 1,5z)
∂L
∂x
= 800x+ 200y − λ1 − λ2
∂L
∂y
= 1600y + 200x+ 400z − λ1 − λ2
∂L
∂z
= 3200z + 400y − λ1 − 1,5λ2
∂L
∂λ1
= 1− x− y − z
∂L
∂λ2
= 1,2− x− y − 1,5z
Resolver el sistema anterior, igualando a 0, se obtiene
x = 0,5
y = 0,1
z = 0,4
λ1 = 1800
λ2 = −1380
Luego, como ∇g1 = (−1,−1,−1) y ∇g2 = (−1,−1,−1,5) son l.i., entonces los valores encontrados son
candidatos al o´ptimo. el valor de la funcio´n objetivo es 390. Para ver que se satisface la condico´n suficiente,
hay que ver si Hf +
∑m
i=1 λiHgi es definido positivo.
Hf (x, y, z) =
 800 200 0200 1600 400
0 400 3200

Hg1(x, y, z) = 0
Hg2(x, y, z) = 0
Y como los valores propios de Hf (x, y, z) son 0.7491 1.5556 y 3.2953 aproximadamente, entonces es defi-
nida positiva en R3.
Si se cambia el retorno esperado a un 12.5%, entonces utilizando la afirmacimacio´n, ∆ = 0,05 y el incre-
mento en la funcio´n objetivo es λ1∆ = 1800 ∗ 0,05 = 90.
5