clase02 220307

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 #2
Dualidad Lagrangiana
22 de Marzo del 2007
Problema 1. Calcule una cota superior para el siguiente problema:
Maximizar xTQx
s.a x2i = 1, i = 1, ..., n
Solucio´n 1. El problema se replantea como:
-Minimizar −xTQx
s.a x2i = 1, i = 1, ..., n
La funcio´n q(u, v) = q(v) es la siguiente:
q(v) = ı´nf
x
{−xTQx+
n∑
i=1
vi(x2i − 1)}
= ı´nf
x
{−xT (Q−Diag(v))x} − vT1
= − sup
x
{xT (Q−Diag(v))x} − vT1
Si Q−Diag(v) es semidefinida negativa, q(v) = −vT1, y q(v) = −∞ en cualquier otro caso (chequear) :
q(v) =
{ −vT1 Q−Diag(v) ≤ 0
−∞ ∼
El problema dual (irrestricto) queda de la forma:
−Maximizarv q(v)
m
Minimizarv −q(v)
m
Minimizarv
{
vT1 Q−Diag(v) ≤ 0
∞ ∼
Luego, la menor cota superior, por dualidad de´bil, es la solucio´n del problema dual, la cual es ı´nf{vT1 : Q−Diag(v) ≤
0}. �
Problema 2 (Reformulacio´n de regio´n factible bajo estabilidad de valor objetivo). Considere el problema
(P ):
(P ) :
 Minimizar f(x)s.a gj ≤ 0 j = 1, ..., r
x ∈ X
y (P˜ ):
(P˜ ) :

Minimizar f(x)
s.a gj ≤ 0 j = 1, ..., r
g˜j ≤ 0 j = 1, ..., r
x ∈ X˜
1
con X = X˜ ∩ {x : g˜j ≤ 0, j = 1, ..., r} y f∗ su valor o´ptimo (comu´n). Pruebe:
1. Si (P˜ ) no tiene gap de dualidad, entonces (P ) tampoco.
2. Si (λ, λ˜) ∈ R2r es multiplicador geome´trico de (P˜ ), entonces λ ∈ Rr es multiplicador geome´trico de (P ).
Solucio´n 2. :
1. Si (P˜ ) no tiene gap de dualidad, entonces
f∗ = sup
(λ,λ˜)≥0
qP˜ (λ, λ˜)
= sup
(λ,λ˜)≥0
ı´nf
x∈X˜
{f(x) + λT g(x) + λ˜T g˜T (x)}
≤ sup
(λ,λ˜)≥0
ı´nf
x∈X˜,g˜j≤0,j=1,...,r
{f(x) + λT g(x) + λ˜T g˜T (x)}
= sup
(λ,λ˜)≥0
ı´nf
x∈X
{f(x) + λT g(x) + λ˜T g˜T (x)}
≤ sup
(λ,λ˜)≥0
ı´nf
x∈X
{f(x) + λT g(x)}
= sup
λ≥0
ı´nf
x∈X
{f(x) + λT g(x)}
= sup
λ≥0
qP (λ)
Por dualidad de´bil se tiene ı´nfx∈X f(x) ≥ supλ≥0 qP (λ), luego, se cumple la igualdad.
2. Si (λ, λ˜) es multiplicador geome´trico de (P˜ ), entonces
f∗ = qP˜ (λ, λ˜)
= ı´nf
x∈X˜
{f(x) + λT g(x) + λ˜T g˜(x)}
≤ ı´nf
x∈X˜,g˜j(x)≤0,j=1,...,r
{f(x) + λT g(x) + λ˜T g˜(x)}
= ı´nf
x∈X
{f(x) + λT g(x) + λ˜T g˜(x)}
≤ ı´nf
x∈X
{f(x) + λT g(x)}
= qP (λ)
Luego, λ es multiplicador geome´trico de (P ), pues por dualidad de´bil, f∗ ≥ qP (λ), y adema´s λ ≥ 0.�
Problema 3 (Control O´ptimo de produccio´n y almacenaje). Una compan˜ia desea planificar la produccio´n de
cierto item hasta un instante T , de manera que la suma de los costos de produccio´n y almacenamiento sea mı´nima.
Adema´s, la demanda , cuyo valor se conoce, debe ser satisfecha; la tasa de produccio´n debe ser al menos l items por
unidad de tiempo y a lo ma´s u items por unidad de tiempo; el inventario no debe exceder los d items; y al final del
per´ıodo de produccio´n deben haber al menos b items. Las variables y datos son los siguientes:
x(t): stock almacenado en el tiempo t (variable)
y(t): tasa de produccio´n en el tiempo t (variable)
z(t): demanda en el tiempo t (dato)
x0: inventario inicial (dato)
c1, c2: coeficientes conocidos (dato)
El modelo no lineal asociado es el siguiente:
Minimizar
∫ T
0
[c1x(t) + c2y2(t)]dt
x(t) = x0 +
∫ t
0
[y(τ)− z(τ)]dτ t ∈ [0, T ]
x(T ) ≥ b
0 ≤ x(t) ≤ d t ∈ [0, T )
l ≤ y(t) ≤ u t ∈ [0, T ]
2
La idea es encontrar la tasa de produccio´n que minimiza la funcio´n objectivo, cuya variable es el stock en la bodega.
La discretizacio´n del problema consiste en dividir el intervalo [0, T ] en K per´ıodos de largo ∆, y denotando
xk = x(∆k), yk = y(∆k) y zk = z(∆k), el problema se aproxima por:
Minimizar
K∑
k=1
[c1xk + c2y2k]
xk = xk−1 + [yk − zk] k ∈ {1, ...,K}
xK ≥ b
0 ≤ xk ≤ d k ∈ {0, ...,K − 1}
l ≤ yk ≤ u k ∈ {1, ...,K}
Formu´le el Dual Lagrangiano del problema discreto.
Solucio´n 3. :
1. Las variables son x = (xk) con k = 0, ...,K e y = (yk) con k = 1, ...,K. Las restricciones de desigualdad son:
g1,k(x, y) = xk − d
g2,k(x, y) = −xk
g3,k(x, y) = yk − u
g4,k(x, y) = l − yk
g5,k(x, y) = b− xK
Las restricciones de igualdad son:
h1,k(x, y) = xk − xk−1 − (yk − zk)
Luego, la funcio´n q(u, v) es la siguiente:
q(u, v) = ı´nf
x,y
{
K∑
k=1
[c1xk + c2y2k] +
5∑
j=1
∑
k
uj,kgj,k +
∑
k
vkh1,k}
El problema dual es
Maximizar ı´nfx,y{
K∑
k=1
[c1xk + c2y2k] +
5∑
j=1
∑
k
uj,kgj,k +
∑
k
vkh1,k}
u ≥ 0
�
3