Upload
vitor-seger-zeni
View
15
Download
0
Embed Size (px)
DESCRIPTION
Aulas do Professor Erlon
Citation preview
Teoria de Otimizaocom Restries
EEL 5102-47: Mtodos Numricos de Otimizao I
Laboratrio de Planejamento de Sistemas de Energia EltricaCentro Tecnolgico Departamento de Engenharia Eltrica
Tel. +55 (48) 3721.9731/9933 Fax +55 (48) 3721.7538Homepage: htto://www.labplan.ufsc.br
Prof.: Erlon Cristian Finardi, D. [email protected]
2Formulao Geral
min ( )
( ) 0, sujeito a:
( ) 0,
nx
i
i
f x
c x i
c x i I
f e ci so funes suaves definidas em um subconjunto que pertence ao n
f a funo objetivo, enquanto ci, i so as restries de igualdade e ci, i I so as restries de desigualdade
Abaixo definido um conjunto vivel que contm todos os pontos x que atendem as restries
{ | ( ) 0, ; ( ) 0, } i ix c x i c x i I
Deste modo possvel escrever o problema acima na forma compacta
min ( ) x
f x
3Caracterizando as Solues
Encontrar o mnimo global uma tarefa rdua em
problemas irrestritos
Adio das restries pode excluir muitos mnimos locais
e facilitar a busca pelo global
Contudo, as restries tambm podem tornar essa tarefa
mais complicada
As restries podem produzir um grande nmero de
solues que no formam um conjunto fechado
Embora, no caso geral, as restries alterem a soluo,
em alguns casos elas no tem efeito na determinao de
um mnimo
4Vrios Mnimos Locais
2
2
2
2
2
min ( )
sujeito a: 1
xf x x
x
Sem a restrio um problema quadrtico estritamente convexo com um nico minimizador em x = 0
Com a restrio, xtal ||x||2 = 1 resolve o problema existindo, portanto, infinitos mnimos globaisRegio Vivel contornos
de f(x)
infinitas solues
5Vrios Mnimos Locais
Sem a restrio o nico minimizador em x = (0,-100)
Com a restrio, vetor (x1,x2)=(k,-1) tal que k=1, 3, 5,... resolve o problema
2
2 22 1
2 1
min ( ) ( 100) 0,01
sujeito a: cos 0
xf x x x
x x
Regio Vivel
contornos de f(x)
vrios mnimos locais
6nico Minimizador
Se a primeira restrio for ignorada, o ponto timo (1,5 1,5)T e f(x) = 0
2
2 21 2
1 2
1
2
min ( ) ( 1,5) ( 1,5)
2 0
sujeito a: 0
0
xf x x x
x x
x
x
Regio Vivel
contornos de f(x)
mnimo globalrestrito
mnimo global
irrestrito
O ponto timo restrito (1,1)T e f(x) = 0,5
7Restries No Interferem na Soluo do Problema
2
2 21 2
1 2
1
2
min ( ) ( 0,5) ( 0,5)
2 0
sujeito a: 0
0
xf x x x
x x
x
x
Regio Vivel
contornos de f(x)
mnimo globalrestrito
mnimo global
irrestrito
O ponto timo deste problema pode ser obtido ignorando-se todas as restries do problema
x=(0,5;0,5)T e f(x) =0
8Definindo Solues Locais
Simples extenses do caso irrestrito, exceto que agora
deve-se levar em considerao os pontos viveis na
vizinhana de x
Um vetor x uma soluo local se x e existe uma
vizinhana V de x tal que f(x) f(x) para x V
Um vetor x uma soluo local estrita (soluo local forte)
se x e existe uma vizinhana V de x tal que f(x) > f(x)
para todo x V com x x
Problemas Somente com Restries de Igualdade
10
Consideraes Iniciais
Introduzir os princpios bsicos que caracterizam as
solues dos problemas com restries de igualdade
Formulao
min ( )
sujeito a: ( ) 0
nx
i
f x
c x
i e I =
Uma restrio no linear
Uma restrio linear
11
Uma Restrio No Linear
= {1} e I = 1 22 21 2
min
s.a: 2 0
x x
x x
T* ( 1, 1)x
( *)f x
1( *)c x
1( )ac x
( )af x
( )bf x
( )cf x
1( )dc x
De qualquer ponto em ,
tal que x x, possvel
realizar um movimento
vivel enquanto f
decrementada
Em x os gradientes da
restrio e da funo
objetivo so paralelos
Existe um escalar tal
que
* * *1( ) ( )f x c x
12
Caracterizao da Soluo1) Para manter a viabilidade deve-se respeitar c1(x+d)=0:
1 1 1 10 ( ) ( ) ( ) ( )T Tc x d c x c x d c x d
2) De forma anloga, para uma direo de descida produzir
um decrscimo em f ento: 0 ( ) ( ) ( )Tf x d f x f x d
Se existe um d que satisfaz 1) e 2) ento possvel ter melhorias
Em consequncia, a condio necessria de otimalidade que no
exista nenhuma direo d que satisfaa 1) e 2) simultaneamente
Com base no exemplo, tem-se que tal direo no pode existir
se f(x) e c1(x) forem paralelos
A condio f(x)=c1(x) no suficiente para encontrar a
soluo tima. No exemplo, essa condio atendida para o
ponto x=(1,1)T ponto de mximo, em que =0,5
13
Uma Restrio Linear
Condio necessria
atendida para um nico
valor de = 3,46
Em problemas com
restries de igualdade no
possvel colocar como
condio adicional que
> 0!
2 21 2
1 2
min 3 4
s.a: 3,5 4 14 0
x x
x x
T* (2,02 1,73)x 1( *)c x
( *)f x
O ponto encontrado um
(nico) mnimo global
14
Funo Lagrangiana
1( , ) ( ) ( )L x f x c x
Problema restrito analisado sob ponto de vista de um
problema irrestrito
Sendo a funo Lagrangeana definida por:
O ponto estacionrio calculado da seguinte maneira:
1( , ) 0 ( ) ( )x x xL x f x c x 1( , ) 0 ( )L x c x
possvel buscar a soluo de um problema com restries de
igualdade calculando os pontos estacionrios da funo
Lagrangiana
Problemas com Restries de Desigualdade Somente
16
Consideraes Iniciais
Em um ponto vivel x a isima restrio de desigualdade, tal que i I, dita estar ativa se
ci(x) = 0 e inativa se ci(x) > 0
Introduzir os princpios bsicos que caracterizam as
solues dos problemas com restries de desigualdade
Formulao
min ( )
sujeito a: ( ) 0
nx
i
f x
c x
i I
17
Uma Restrio No Linear
O vetor gradiente da
restrio, nos pontos onde
a mesma est ativa,
sempre aponta para o
interior da regio vivel
1 2
2 21 2
min
s.a: 2 0
x x
x x
Regio Invivel
T* ( 1, 1)x
1( *)c x
( *)f x
( )bf x
( )cf x
1( )dc x
1( )ac x
( )af x
A condio f(x)=c1(x)
atendida nos pontos
x = (1,1)T com = 0,5
x =(1,1)T com = 0,5
Porm, o sinal de um
importante parmetro
para encontrar uma
soluo
18
Caracterizao da Soluo1) Para manter a viabilidade deve-se respeitar:
1 1 1 1 10 ( ) ( ) ( ) ( ) ( ) 0T Tc x d c x c x d c x c x d
2) Direo de descida: ( ) 0Tf x d
Para encontrar d que satisfaz 1) e 2) simultaneamente
necessrio analisar dois casos:
x um ponto tal que c1(x) > 0. Neste caso d atende 1), dado que
seja suficientemente pequeno. A nica situao onde no possvel
atender 1) e 2) com f(x)=0
x um ponto tal que c1(x) = 0. Assim 1) e 2) tornam-se f(x)Td < 0
e c1(x)Td 0. A nica situao onde essas duas regies no tem
nenhum ponto em comum quando f(x) e c1(x) apontam na
mesma direo, isto , quando:
1( ) ( ), com 0.f x c x
19
Duas Restries
ci(x*)Td 0, i =1,2,
so satisfeitas com d no
quadrante definido por
c1(x*) e c2(x*)
1 2
2 21 2
2
min
s.a: 2 0
0
x x
x x
x
Regio Invivel
2( *)c x
1( *)c x
( *)f x
T* ( 2 ,0)x
2( )ac x
1( )ac x
( )af x
Vetores neste quadrante
atendem a f(x*)Td 0
1 2
1 02 2( *) , ( *) , ( *)
1 10f x c x c x
1
* 2 2
1
20
No Linearidade Acentuada
1 2
2 21 2
min
s.a: 2 0
x x
x x
1 2
2 2 21 2
min
s.a: ( 2) 0
x x
x x
Os dois problemas possuem o ponto timo em x= (1,1)T
Em (2) tem-se que c1(x) = 0 para todos pontos viveis e
f(x)=c1(x) no pode ser assegurado
(1) (2)
Definio: Dado um ponto x* e um conjunto A(x*), diz-se
que as restries esto qualificadas se {ci(x), i A(x*)} so
linearmente independentes
Se a condio acima for verificada, nenhum dos elementos de
{ci(x), i A(x*)} nulo. Ainda, permite expressar as
condies de otimalidade para um problema de programao
no linear qualquer
Condies de Otimalidade de Primeira Ordem
22
Condies Necessrias de Primeira Ordem
Seja x* um mnimo local e que as restries ativas
em x* esto qualificadas. Assim, existe um vetor *,
i I , tal que as seguintes condies so
satisfeitas em (x*, *)
xL(x*, *) = 0
ci(x*) = 0 i
ci(x*) 0 i I
*i 0 i I
*i ci(x*) = 0 i I
Condies de Karush-Kuhn-Tucker (KKT)
23
Condies de KKT - Ilustrao
2 4
1 2
1 1 2
2 1 2
3 1 2
4 1 2
3 1min ( )=
2 8
( ) : 1 0
( ) : 1 0s.a:
( ) : 1 0
( ) : 1 0
f x x x
c x x x
c x x x
c x x x
c x x x
1( )c x
2( )c x
3( )c x
4( )c x
Regio Vivel
1 2
11 1
* (1,0) ( *) , ( *) , ( *)11 1
2
x f x c x c x
T3 1
* 0 04 4
Condies de Otimalidade de Segunda Ordem
25
Introduo... (1)
Condies de KKT indicam como as derivadas primeiras
de f(x) e das restries ativas esto relacionadas em x*
Quando as condies de KKT so verificadas, um
movimento de qualquer vetor w F1 faz com que
wTf(x*)>0 ou wTf(x*)=0, onde
1
( *) 0,| 0,
( *) 0, ( *)
Ti
Ti
d c x iF d
d c x i A x I
Para direes w F1 tal que wTf(x*)=0, no possvel
determinar da informao de primeira ordem se um
movimento nesta direo ir incrementar ou diminuir a
funo objetivo
26
Dado F1 e algum multiplicador de Lagrange * que satisfaz
as condies de KKT, define-se um subconjunto F2(*) de
F1 por
Introduo... (2)
T
T *2
T *
( *) 0, ,
( *) ( *) 0, ( *) com 0,
( *) 0, ( *) com 0.
i
i i
i i
c x w i
w F c x w i A x I
c x w i A x I
Portanto, F2(*) contm direes de F1 que no informam,
com base nas derivadas primeira, se f(x*) ir aumentar ou
diminuir
27
Teorema: Seja x* uma soluo local e que os
gradientes das restries ativas sejam linearmente
independentes. Seja * um vetor de multiplicadores de
Lagrange tal que as condies de KKT so verificadas
e seja F2(*) conforme definido anteriormente. Ento,
Condies Necessrias
Envolvem as derivadas de segunda ordem: se x* uma
soluo local, ento a curvatura da funo Lagrangiana
nas direes de F2(*) devem ser no negativas
T2( *, *) 0, para ( *).xxw L x w w F
28
Teorema: Suponha que para x* vivel n existe um
vetor *, i I , tal que as condies de KKT so
satisfeitas. Suponha tambm que
Ento x* um mnimo local
Condies Suficientes
So condies em f e ci que asseguram que x* uma
soluo local em oposio s condies necessrias que
assumem que x* uma soluo e deduzem propriedades
em f e ci
T2( *, *) 0, para ( *), 0.xxw L x w w F w
29
Exemplo 12 2
1 2 1 1 2min ( ) s.a: ( ) 2 0f x x x c x x x 2 2
1 2 1 2( , ) (2 )L x x x x x
fcil verificar que as condies de KKT so satisfeitas
em x* =(1,1)T com *=1/2. A hessiana de L(x*,*)
** * 1
1 *1
1 02 0( , )
0 10 2xxL x
Essa matriz Definida Positiva para qualquer w 0, e
portanto, certamente satisfaz as condies do teorema
mostrado no slide anterior
Assim x* uma soluo estrita do PNL de fato, uma soluo global dado que o PNL convexo
30
Exemplo 2
Condies de KKT so satisfeitas em xa =(1,1)T com
a*= 1/2 e em xb =(1,1)
T com b*=1/2. As hessianas so
1 0 1 0( , ) e ( , )
0 1 0 1xx a a xx b bL x L x
xa uma soluo estrita do PNL De fato, uma soluo
global, pois xb no atende as condies de segunda ordem
e no existem outros pontos que atendem as condies de
primeira ordem
Adicionalmente, a regio vivel limitada
2 21 2 1 1 2min ( ) s.a: ( ) 2 0f x x x c x x x
2 21 2 1 2( , ) ( 2)L x x x x x
31
Regio Vivel
2 21 2
2 21 2
min 0,1( 4)
s.a: 1 0
x x
x x
1 1
2 2
0,2( 4) 2( , )
2 2
0,2 2 0( , )
0 2 2
x
xx
x xL x
x x
L x
x* = (1,0)T atende KKT em *
= 0,3
Note que c(x*)=(2,0)T, ento:
2 2
22
( *, *)
0 0,8 0 0
0 1,4
1,4 0
Txx
T
w L x w
w w
w
x* = (1,0)T um mnimo local
Exemplo 3... (1)
32
x* = (1,0)T um mnimo global? Uma vez que o problema no
convexo deve-se verificar se existem outros pontos que atendem as
condies de 1 e 2 ordem
Exemplo 3... (2)
1 1 2 21 2
2 2
0,2( 4) 2 0, 1 0
2 2 0x
x xL L x x
x x
Condies de KKT
De xL=0 (segunda equao) tem-se que =1 ou x2=0. Com x2=0
chega-se ao ponto testado no slide anterior. Com =1 obtm-se da
primeira equao de xL que x1=0,3636 e, aplicando-se na equao
yL tem-se x2 = 0,9315
Portanto dois pontos adicionais atendem as condies de KKT
xa=(0,3636 0,9315)T com =1
xb=(0,3636 -0,9315)T com =1
33
Exemplo 3... (3) Considerando xa=(0,3636 0,9315)
T com =1, tem-se
T1 2
0,7273( ) ( ) 0 2,5617
1,8631a ac x c x w w w
T
T
2 2 22
2 2
( , )
2,5617 2,2 0 2,561714,4371 0
0 0
xx aw L x w
w ww
w w
Portanto, xa no um ponto de mnimo, pois a funo
Lagrangiana tem curvatura negativa
Uma vez que neste problema a curvatura no depende do valor das
variveis primais, ento xb tambm no representa uma soluo local
Embora x* = (1,0)T seja um mnimo local, a f(x) no limitada
inferiormente na regio vivel e, portanto, no existe soluo global
34
2
2 21 2
3max ( ) ( 1) 2
4xf x x x
21 1 2s.a : ( ) : 2 4 0c x x x
2 1( ) : 5c x x
Exemplo 4... (1)2
2 21 2
3min ( ) ( 1) 2
4xf x x x
21 1 2s.a : ( ) : 2 4 0c x x x
2 1( ) : 5 0c x x
2( )c x
1( )c x
35
Somente c1(x) ativa
De (2) tem-se x2 = 0 ou = 1.
Com x2 = 0, pode-se obter por (3) x1 = 4. Note que c2(x) > 0. De (1) tem-se que = 4,5. Assim, x = (4,0)T atende KKT
Considerando x = (4,0)T e = 4,5 as condies de segunda ordem so
1
2 2
1,5( 1) 10
4 4x
xL
x x
1
2 2
21 2
1,5 1,5 0
4 4 0
2 4 0
x
x x
x x
(1)
(2)
(3)
Exemplo 4... (2)
1 22 2
2 2
1,5 0 01 4 0 0, 0 0, 14 0
0 14
ww w
w w
Assim, x = (4,0)T um ponto de mnimo local estrito
36
...continuando...
Com = 1, pode-se obter por (1) que x1 = 5/3. Note que c2(x) > 0. De (3) tem-se que x2 = 1,0801.
Considerando x = (5/3 1,0801)T e = 1 as condies de segunda ordem so
1
2 2
1,5( 1) 10
4 4x
xL
x x
1
2 2
21 2
1,5 1,5 0
4 4 0
2 4 0
x
x x
x x
(1)
(2)
(3)
Exemplo 4... (3)
1 2 22 2 2
2 2
1,5 0 4,321 4,32 0, 4,32 0, 28 0
0 0
w ww w w
w w
Assim, x = (5/3 1,0801)T no um ponto de mnimo local estrito
37
Considerando x = (5/3 1,0801)T e = 1
Exemplo 4... (4)
1 2 22 2 2
2 2
1,5 0 4,321 4,32 0, 4,32 0, 28 0
0 0
w ww w w
w w
Assim, x = (5/3 1,0801)T no um ponto de mnimo local estrito
x* = (4,0)T um mnimo global?
Embora seja o nico ponto de KKT que atende a segunda ordem, deve-
se verificar se o valor de f(x) na regio vivel limitada inferiormente
Note que f(x*) = 6,75. Pode-se fixar x1 = 4 em c1(x). Assim x2 = 2 e
f(4,2) = 14,75 < f(x*)
Portanto, x* no um mnimo global
OBRIGADO!
Prof. Erlon Cristian Finardi [email protected]