clase03 300307

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 #3
Conos Polar, Tangente y Normal, Condiciones Necesarias de Optimalidad
30 de Marzo del 2007
Definicio´n (Cono Polar Negativo). Sea C ⊂ Rn. Se llama cono polar negativo de C al conjunto
C− = {d ∈ Rn : dTx ≤ 0,∀x ∈ C}
Definicio´n (Cono Polar Negativo). Sea C ⊂ Rn. Se llama cono polar positivo de C al conjunto
C+ = {d ∈ Rn : dTx ≥ 0,∀x ∈ C}
Notar que C+ = −C−.
Definicio´n (Cono de Direcciones Factibles). Sea C ⊂ Rn y x ∈ C. Se llama cono de direcciones factibles de C en
x al conjunto
FC(x) = {d ∈ Rn : ∃δ > 0, x+ λd ∈ C,∀λ ∈ (0, δ), d 6= 0}
Definicio´n (Cono Normal). Sea C convexo y x ∈ C. Se llama cono normal a x ∈ C al conjunto
NC(x) = {d ∈ Rn : dT (x− x) ≤ 0,∀x ∈ C}
Definicio´n (Cono Tangente). Sea C convexo y x ∈ C. Se llama cono tangente a x ∈ C al conjunto
TC(x) = {d ∈ Rn : ∃(xk) ⊂ Rn, xk → d, ∃(λk) ∈ R+, λk > 0, λk → 0, tal que x+ λkxk ∈ C,∀k}
Proposicio´n. :
1. NC(x) es cerrado convexo y contiene al cero.
2. NC(x) = T−C (x)
3. x ∈ int(C) =⇒ NC(x) = Rn
4. Sea x ∈ C1 ∩ C2. Entonces NC1(x) +NC2(x) ⊂ NC1∩C2(x).
5. NC1×C2(x1, x2) = NC1(x1)×NC2(x2)
6. NC1+C2(x1 + x2) = NC1(x1) ∩NC2(x2)
Demostracio´n. :
1. Sea (dk) ⊂ NC(x) tal que dk → d. Supongamos d /∈ NC(x), es decir, ∃K tal que dk /∈ NC(x),∀k ≥ K, lo cual
es una contradiccio´n. Luego NC(x) es cerrado.
Sean d1, d2 ∈ NC(x), λ ∈ [0, 1]. Se tiene que:
(λd1 + (1− λ)d2)T (x− x) = λdT1 (x− x) + (1− λ)dT2 (x− x)
≥ 0
Luego NC(x) es convexo.
Claramente 0 ∈ NC(x), pues 0T (x− x) ≥ 0.
2. Sea d ∈ TC(x)−, es decir, ∀p ∈ TC(x), dT p ≤ 0. Como p ∈ TC(x) = cl(FC(x)), esta´n inclu´ıdas las direcciones
factibles de la forma x− x, x ∈ C, pues C es convexo, luego dT (x− x) ≤ 0,∀x ∈ C, es decir, x ∈ NC(x).
Sea d /∈ TC(x)−, es decir, ∃p ∈ TC(x), dT p > 0. Sabemos que p ∈ TC(x) = cl(FC(x)), luego, si p ∈ FC(x), es
de la forma x − x con x ∈ C, y se tendr´ıa dT (x − x) > 0, lo cual indica d /∈ NC(x). Ahora, si p ∈ ∂FC(x),
existe una sucesio´n (pk) ∈ FC(x) tal que pk → p, luego, 0 < dT p = l´ımk dT pk, es decir, ∃K tal que ∀k ≥ K,
dT pk > 0 y como pk se puede escribir como xk − x con xk ∈ C, se cumple d /∈ NC(x).
1
3. Como x ∈ int(C), se tiene FC(x) = Rn, luego, cl(FC(x)) = Rn, y por lo tanto, TC(x) = Rn. Como (Rn)− = Rn,
se tiene TC(x)− = Rn. El resultado se tiene por el punto anterior.
4. Propuesto.
5. Propuesto.
6. Propuesto.
Proposicio´n. Las condiciones necesarias de primer orden son equivalentes a cada una de las siguientes afirmaciones:
1. ∇f(x)T d ≥ 0,∀d ∈ TC(x)
2. −∇f(x) ∈ NC(x)
Demostracio´n. Ya se vio´ en ca´tedra la equivalencia con el punto (1). Veamos la equivalencia con el punto (2).
Supongamos x es o´ptimo local. Por propiedad (2) de la proposicio´n anterior, NC(x) = TC(x)−, luego, si la condicio´n
no se cumple, existe p ∈ TC(x) tal que −∇f(x)T p > 0 o equivalentemente ∇f(x)T p < 0. Como cl(FC(x)) = TC(x),
existen sucesiones (xk) ∈ Rn y (λk) tales que xk → p, λk → 0 y x+ λkxk ∈ C para todo k.
Como sabemos que
l´ım
k→∞
f(x+ λkxk)− f(x)−∇f(x)t(λkxk)
‖λkxk‖ = 0
se tiene que existe un K tal que ∀k ≥ K,∇f(x)t(λkxk) < 0 (o equivalentemente −∇f(x)t(λkxk) > 0), luego
necesariamente f(x+ λkxk)− f(x) < 0 a partir de un K˜ grande. Esto u´ltimo contradice la o´ptimalidad local de x.�
Proposicio´n. Sea C convexo cerrado. Entonces NC(x) = C− ∩ {x}⊥ = {z ∈ C− : z ⊥ x}
Demostracio´n. Sea d ∈ Rn tal que dTx = 0 y dTx ≤ 0,∀x ∈ C. Restando, se obtiene dT (x− x) ≤ 0,∀x ∈ C.
La otra implicancia queda propuesta.�
Podemos aplicar lo anterior al siguiente tipo de problemas:
mı´n
x∈Rn
{f(x) : xi ≥ 0, i = 1, ..., n}
El conjunto C es igual a Rn+, luego
(CNPO) ⇐⇒ −∇f(x) ∈ NRn+(x) ∧ x ∈ Rn+
⇐⇒ −∇f(x) ∈ (Rn+)− ∩ {x}⊥ ∧ x ∈ Rn+
⇐⇒ −∇f(x) ∈ Rn− ∩ {x}⊥ ∧ x ∈ Rn+
⇐⇒ −∇f(x) ∈ Rn− ∧ −∇f(x)Tx = 0 ∧ x ∈ Rn+
⇐⇒ ∇f(x) ∈ Rn+ ∧∇f(x)Tx = 0 ∧ x ∈ Rn+
Luego,
(CNPO)⇐⇒
 x ≥ 0∇f(x) ≥ 0∇f(x)Tx = 0
Problema 1. Encuentre un o´ptimo global del siguiente problema:
mı´n
x∈R2
{x21 + 2x1x2 + 2x22 − x1 : x1, x2 ≥ 0}
Solucio´n 1. Veamos la convexidad:
∇f(x) =
(
2x1 + 2x2 − 1
2x1 + 4x2
)
∇2f(x) =
(
2 2
2 4
)
� 0
Luego es estrictamente convexa. Si encontramos un mı´nimo, sera´ u´nico.
Las condiciones necesarias de primer ordenson equivalentes a:
(CNPO)⇐⇒

x1, x2 ≥ 0
2x1 + 2x2 − 1 ≥ 0
2x1 + 4x2 ≥ 0
(2x1 + 2x2 − 1)x1 = 0
(2x1 + 4x2)x2 = 0
2
Tenemos que:
2x1 + 4x2 = 2(x1 + x2) + 2x2
≥ 21
2
+ 2x2
≥ 1 + 2x2
> 1
Luego x2 = 0 y x1 > 0. Finalmente 2x1 − 1 = 0 y x1 = 1/2.�
3