IA543 - Otimizac~ao N~ao-Linear
Lista de Exerccios - Captulo 7
1. Considere a matriz A 2 Rm n m > n. Uma soluc~ao x para o sistema de
equaco~es inconsistentes Ax = b rank(A) = n, pode ser obtida resolvendo-se
1
2
minimizar kAx ; bk22 :
Mostre que a soluc~ao deste problema pode ser escrita na forma x = A# b, onde
A# e uma matriz n m que satisfaz a identidade A# A = I . A matriz A# e
chamada de pseudo-inversa de A,
2. Determine a soluc~ao otima de
1
2
minimizar kxk22 s.a Ax = b
onde A 2 Rm n rank (A) = m m < n. A soluc~ao do problema e a soluc~ao de
norma mnima do sistema de equac~oes Ax = b.
3. Considere o problema de otimizac~ao
maximizar f (x) s.a Ax = b
onde A 2 Rm n rank (A) = m < n b 2 Rm e f : Rn ! R e uma func~ao
diferenciavel e c^oncava. Considere ainda a matriz P := I ; AT (AAT );1 A P 2
Rn n . Mostre que se P rf (x0) = 0, ent~ao x0 e um maximo global de f sujeito
a Ax = b.
4. Considere o seguinte problema de otimizac~ao:
1
2
minimizar (x1 ; 1)2 + x22 ] s.a ; x1 + x22 = 0
onde 2 R e uma constante.
1
a) Determine os pontos que satisfazem as condic~oes de 1a. ordem do problema
b) Determine os valores de para os quais o ponto x1 = x2 = 0 e um mnimo
local do problema. Interprete gracamente o resultado.
5. Considere o problema
minimizar x21 + x22 + x23 s.a x21 +
x22 + x32 = 1:
4
9
a) Determine todos os pontos que satisfazem as condic~oes de primeira ordem
associadas ao problema
b) Determine a natureza das soluco~es estacionarias obtidas no item anterior
atraves das condic~oes de segunda ordem.
6. Considere matrizes A = AT 2 R2
2
descritas na forma
"
#
A = aa11 aa12 :
12
22
Uma matriz simetrica 2 2 e semi-denida positiva se e somente se a11 0,
2 0. Use este resultado para vericar se a hessiana da
a22 0 e a11 a22 ; a12
func~ao
f (x1 x2 ) := (x2 ; x21 )2
e semi-denida positiva em := f(x1 x2 ) : x2 x21 g.
7. Considere a func~ao f : R2 ! R denida por
f (x1 x2 ) = x21 + 2x1 x2 ; 3x22 + x1 + x2 :
a) Determine rf (x)T d para x = (0 1) e d = (1 1)
b) O ponto x = (0 1) e um mnimo local de f em
:= f(x1 x2) : x1 0 x2 0g ?
Justique.
2
8. Seja o problema de otimizac~ao
1
2
minimizar (x1 ; )2 ; x1 ; x2 s.a x1 x22 x21 + x22 2:
a) Esboce a regi~ao factvel do problema e determine o conjunto dos pontos em
que ambas as restric~oes est~ao ativas
b) Selecione o ponto com componentes positivas e determine os valores de para
os quais o ponto selecionado satisfaz as condic~oes necessarias de 1a. ordem
c) Para os valores de determinados em b), o ponto selecionado e um mnimo
global do problema ? Justique.
9. Use as condic~oes sucientes de 2a. ordem para resolver o seguintes problemas de
otimizaca~o:
a) maximizar 14x1 ; x21 + 6x2 ; x22 + 7 s.a x1 + x2 = 2
b) maximizar x1 + x2 s.a x21 + x22 = 1
10. Resolva o problema de otimizac~ao
minimizar (x1 ; 1)2 + x22 s.a 4x1 ; x22 = 0
a) eliminando diretamente uma das variaveis
b) utilizando condic~oes de otimalidade.
11. Considere o problema
minimizar f (x) s.a 2x1 + x2 = c
onde f (x) := x21 + x22 e c 2 R e uma constante. Determine
a) x(c), a soluc~ao otima parametrizada por c
b) (c), o multiplicador otimo de Lagrange parametrizado por c
3
c) f (x(c)), o valor otimo de f . Mostre que
d
dc f (x(c)) = ;(c)
e interprete este resultado.
12. Resolva atraves das condic~oes de otimalidade
3
9
minimizar ff (x) = x1 + x2 g
2
2
s.a h1 (x) = 2x1 + 3x2 = 12
h2 (x) = ;x1 + 3x2 = 3
13. Considere o seguinte problema:
9
minimizar (x1 ; )2 + (x2 ; 2)2
4
s.a x21 ; x2 0
x1 + x2 6
x1 x2 0
a) Verique que x0 = (3=2 9=4) satisfaz as condico~es de 1a. ordem do problema
b) Interprete gracamente as condic~oes de 1a. ordem no ponto x0 c) Mostre que x0 e a soluc~ao global unica do problema.
14. Considere o seguinte problema
maximizar cT d s.a dT d 1
onde c 2 Rn e qualquer vetor n~ao-nulo dado.
a) Mostre que a soluc~ao do problema e d0 = c=kc k
b) Interprete a soluc~ao encontrada no caso em que c e o gradiente de alguma
func~ao diferenciavel f : R ! R num ponto qualquer x0 2 Rn (c = rf (x0)).
4
15. O resultado a seguir foi demonstrado experimentalmente por Josiah Willard Gibbs
em 1876, ao analisar problemas de equilbrio de subst^ancias heterog^eneas. Suponha que x0 resolve o seguinte problema
minimizar
s.a
Dena i :=
n
X
i=1
n
X
fi(xi )
xi = 1
i=1
xi 0 i = 1
2 ::: n
@ f (x0 ). Mostre que existe um escalar tal que
@xi i
i e (i ; )x0i = 0 i = 1 2 : : : n:
16. Use as condico~es de otimalidade para mostrar que a media aritmetica de n escalares
positivos e maior ou igual do que a sua media geometrica, isto e,
n
1X
n xi i=1
n
Y
xi
i=1
!1=n
xi > 0 i = 1 2 : : : n
Sugest~ao: considere o problema de otimizac~ao
n
1X
minimizar
n xi s.a
i=1
n
Y
i=1
xi
!1=n
=p p2R
17. Mostre que a desigualdade da media aritmetica-geometrica pode ser generalizada
no seguinte sentido: se 1 2 : : : n s~ao n numeros n~ao-negativos tais que 1 +
2 + + n = 1, ent~ao
n
Y
xi
i=1
i n
X
i=1
i xi :
Sugest~ao: dena f (x) = ; ln(x) para x > 0 e use a desigualdade de Jensen:
se f e uma func~ao convexa sobre um domnio convexo C , ent~ao para quaisquer
5
x1 x2 : : : xn 2 C e quaisquer 1 2 : : : n n~ao-negativos tais que 1 + 2 +
+ n = 1,
f
n
X
i=1
!
ixi n
X
i=1
i f (xi ):
Sob que condic~ao a desigualdade se transforma numa igualdade ? Justique.
18. Mostre que a soluc~ao do problema geometrico
minimizar c1 x21 + c2 x1 x2 s.a 1 ; x;1 2 x;2 1 0
onde c1 e c2 s~ao constantes positivas, e
1
2
x1 (c1 c2 ) = 2cc2 3 x2 (c1 c2 ) = 2cc1 3
1
2
Faca a substituic~ao y1 := ln(x1 ) y2 := ln(x2 ) e mostre que o problema resultante
e convexo e equivalente ao original.
19. Escreva as condico~es de otimalidade do problema
maximizar f (x)
s.a h(x) = 0
g(x) 0:
20. Considere o problema
minimizar f (x) s.a x 0
onde f : Rn ! R e uma func~ao convexa diferenciavel. Seja x um dado ponto e
g := rf (x). Mostre que x e uma soluc~ao otima do problema se e somente se
d = 0, onde d e denida por (i = 1 2 : : : n)
8
>
<
di = >
:
;gi se xi > 0 ou gi < 0
0 se xi = 0 e gi 0:
6
21. Considere o problema
minimizar x21 + x22 s.a g(x) = 2x1 + x2 ;4
a) Determine a func~ao dual e represente-a gracamente
b) Determine as soluc~oes primal e dual otimas x e verique que n~ao ocorre
gap
de dualidade no problema. Justique a inexist^encia de gap d () = g(x ) no ponto = .
c) Verique que d
22. Considere o problema primal
1
2
1
2
minimizar x21 + x22 + x1 s.a x1 0
a) Obtenha os pontos que satisfazem as condic~oes de primeira ordem do problema
para = +1 e = ;1, respectivamente. Formule o problema dual min-max
associado ao problema primal
b) Para um dos valores de e possvel obter a soluc~ao do problema primal a partir
da soluc~ao do problema dual. Resolva o problema dual e obtenha a soluc~ao
primal correspondente.
7