03 - Metodos de Busca Linear

Mtodos de Busca Linear

EEL 6000 - Mtodos Numricos de Otimizao

Laboratrio de Planejamento de Sistemas de Energia EltricaCentro Tecnolgico Departamento de Engenharia Eltrica

Tel. +55 (48) 331.9731/9933 Fax +55 (48) 331.7538Homepage: htto://www.labplan.ufsc.br

Prof.: Erlon Cristian Finardi, D. [email protected]

Tcnicas para a Operao de SEE 22EEL6000 Mtodos Numricos de Otimizao

Viso Geral dos Algoritmos

conhecimento da aplicao ou arbitrariamente

partir de x0 construda uma sequncia

Para realizar xk xk+1 faz-se uso de f(xk) e/ou f(x0),f(x1),..., f(xk-1)

Objetivo: Descobrir xk+1 tal que f(xk+1) < f(xk) at que fk 0

x0

0{ }k kx


Duas Estratgias Busca Linear

Escolhe pk que seja de descida fkTpk < 0 Minimiza f(x) na direo pk minf(xk+k pk), k > 0

Regio de Confiana

Faz uso de um modelo mk que aproxima f(x) ao redor de xk Restringe-se o minimizador de mk na vizinhana: xk min

mk(xk +pk), pk > 0, em que xk + pk est dentro de uma regio de confiana (e.g., || pk ||2 , > 0)


Duas Estratgias Exemplo2 2 2

2 1 110 1( ) ( ) ( )f x x x x= - + -

- - + - = - 2

1 2 1 12

2 1

40 2 220

( )( )

( )x x x x

f xx x

- + - = - 21 2 12

1

120 40 2 4040 20

( )x x x

f xx


Busca Linear Exemplo... (1)T0 1( , )kx =

220

( )k kdx f x =- = -

T1 0( , )ky =-=-

=

2 1

0

1

[ ( )] ( )k k kdy f y f y

f(xk)=11xk

dxk

f(yk)=10yk

dyk


Busca Linear Exemplo... (2)2 2 2 2

1010 1 20 4 1 4min ( ) ( ) ( ) ( )

kk k k k kf x f+a > = a = - a - a + - a

0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.160

5

10

15

20

25

30

35

40

45

k

f(k)


Busca Linear Exemplo... (3)+a >= a = a - 210 10 1min ( ) ( ) ( )k k k kf y f

k

f(k)

0 0.5 1 1.5 2 2.5 30

5

10

15

20

25

30

35

40


Regio de Confiana ... (1) Modelo que aproxima f(x) em xk = (0,1)T

T T12

( )k k k k k k k km x p f p f p B p+ = + + Considerando Bk = 2f(xk) tem-se

T T2 38 011120 0 202

( )k k k k km x p p p p - - + = + +

1 2

2 21 2 1 2

2

2

19 10 2 20 11

( , )min

. :

Tk k k

k k k k kp p p

k k

m p p p p

s a p

==- + - + +

D

Problema


Regio de Confiana ... (2)

kxkp

kp1( )km x =

19( )km x =

contornos do modelo

contornos de f(x)

mnimo de f(x)

mnimos de m(xk)


Direes Busca Linear

Principais Classes de Algoritmos

Gradiente Steepest-Descent onde Bk a matriz identidade

Newton, em que Bk a matriz hessiana

QuaseNewton, onde a Bk uma aproximao (Definida Positiva) da matriz hessiana, atualizada em cada iterao

Gradiente Conjugado pk = fk +k pk-1, onde k um escalar que garante que pk e pk-1 so direes conjugadas

Em geral, so do tipo pk = [Bk]1 fk Onde Bk uma matriz simtrica e no-singular


Escolha do Tamanho do Passo Tradeoff (k que reduz f(xk)

substancialmente) x (mnimo esforo nessa escolha)

Idealmente: mnimo global de () = f(xk+kpk), k > 0 Soluo: realizar um busca linear inexata que

reduza f(xk) adequadamente um mnimo custo computacional

Descobrir um intervalo que possui valores desejveis para k Calcular um bom valor de k que pertence ao intervalo definido

acima


Dificuldades para Encontrar k( )k

kPrimeiro Ponto

Estacionrio

Primeiro Mnimo Local

Mnimo Global

( ) ( 0)k kf x f


Reduo Insuficiente Uma simples condio

poderia ser imposta em k para reduzir a funo objetivo:f(xk + k pk) < f(xk)

No apropriada pois, na figura, onde x*=1, a seqncia de valores de f(x), definida por {5/K}, converge para zero


Decrscimo Suficiente f(xk + kpk) f(xk) + c1kfkTpk c1 (0,1) Proporcional a k e a derivada direcional fkTpk

(Condio de Armijo)

Na prtica c1 da ordem de 110-4

Condio de Decrscimo Suficiente

() l()

( ) ( )k kf x p

T1( ) ( )k k kl f x c f p

No garante que um algoritmo tenha

um razovel progresso pois

pode ser atendido para valores muito

pequenos de


Condio de Curvatura f(xk + pk)T pk c2fkTpk c2 (c1,1) '() maior do que c2'(0)( ) ( )k kf x p

c2fkTpk = c2'(0)

fkTpk = '(0)

Se '() muito negativa, pode-se reduzir f(x)significativamente

Caso contrrio, no se espera reduzir f(x) em pke pode-se terminar a busca em


Condies de Wolfef(xk + pk) f(xk) + c1fkTpk e f(xk + pk)T pk c2fkTpk( ) ( )k kf x p

0


Algoritmos para Seleo de Considerao Inicial: '(0) < 0 Se f(x) = 0.5xTQx + bTx + c (convexa)

k= (fkTpk)/(pkTQpk) o mnimo global em xk+pk Procedimento Geral

Requer uma estimativa de 0 - Passo Inicial Constri um sequncia { i } que termina se as condies de

Fortes de Wolfe (ou Armijo) podem ou no ser atendidas Duas Fases

1. Descobrir um intervalo [a,b] com valores aceitveis para 2. Calcular um bom valor de que pertence ao intervalo definido

acima (interpolao, por exemplo)


Determinao do Passo Inicial 0 = 1 para os Mtodos de Newton e Quase-Newton Para mtodos que no produzem direes dessa

qualidade (e.g., Gradiente e Gradiente Conjugado) necessrio utilizar alguma informao do problema

0= k-1 (fk-1Tpk-1)/(fkTpk) Interpolar uma quadrtica a partir de f(xk-1), f(xk) e'(0) = fkTpk definindo 0 como o respectivo

minimizador

10

2 ( ) ( )'(0)

k kf x f x


Backtracking Line SearchEscolha > 0, , c1 (0,1). Inicialize = Repita at Verificar f(xk + pk) f(xk) + c1fkTpk

= End (Repita)

k = = 1 para Newton e Quase-Newton (diferentes valores para Gradiente

e Gradiente Conjugado) Na prtica pode variar em cada iterao interpolao (adiante)

Deve-se garantir que [low, high], tal que 0 < low< high< 1 Algoritmo garante que algum valor fixado inicialmente ou

pequeno (mas no muito) o suficiente para atender a condio de decrscimo suficiente

Adequado para Newton. Menos apropriado para Quase-Newton e Gradiente


Interpolao...(1) Baseada em valores conhecidos da funo e de

suas derivadas Pode ser visto com um aprimoramento do algoritmo de

backtracking Objetivo

Descobrir que satisfaz as condies de decrscimo suficiente, sem ser muito pequeno

Procedimento que fornece valores decrescentes de , de modo que no seja muito menor que seu predecessor

Condio de decrscimo suficiente(k) (0) + c1k'(0)

eficiente pois calcula f(x) o mnimo possvel


Dado 0, se (0) (0) + c10 '(0), pare. Caso contrrio, em [0,0] contm um passo aceitvel

Com (0), '(0) e (0) realiza-se a seguinte interpolao quadrtica

20 020

( ) (0) '(0)( ) '(0) (0)q

20

10 0

'(0)2 ( ) (0) '(0)

cujo mnimo dado por

Se a condio (1) (0) + c11 '(0) atendida, ento a busca terminada. Caso contrrio, constri-se uma funo cbica com base em (0), '(0), (0) e (1)

Interpolao...(2)


Funo cbica

Interpolao...(3)3 2 0 0( ) '( ) ( )c a b

2 21 10 1

2 2 3 30 00 1 1 0 0 1

( ) (0) '(0)1( ) (0) '(0)( )

ab

onde

Diferenciando c() encontra-se o mnimo 2 [0,1] 2

23 '(0)

3b b a

a

Se necessrio, deve-se fazer uma nova interpolao cbica com (0), '(0) e os dois mais recentes valores de at satisfazer o decrscimo suficiente

Se qualquer i muito prximo ou muito menor que i-1 , ento faz-se i=i/2 (Safeguard)


Algoritmo de WolfeEscolha 1 > 0 e max. Faa 0 = 0 e i = 1Repita (i 10)

Avalie (i)Se (i) > (0) + c1i '(0) ou [(i) (i-1) e i >1]

ZOOM(i-1 , i) * e PAREAvalie '(i)Se |'(i)| c2'(0)

Faa i = * e PARESe '(i) 0

ZOOM(i, i-1 ) * e PAREEscolha i+1 (i , max) e faa i=i+1

End (Repita)


ZOOM(lo , hi)a. O intervalo (lo , hi) que atende as condies de Wolfeb. lo d o menor da funo objetivo at a presente iterao e atende decrscimo suficientec. hi escolhido de modo que '(lo)(hi lo) < 0

Repita ( j 10 )Interpole (Quadrtica ou Cbica) para descobrirum valor candidato j (lo , hi)

Avalie (j)Se [(j) > (0) + c1j '(0)] ou [(j) (1o)]

Faa hi = jSeno

Avalie '(j)Se |'(j)| c2'(0)

Faa * = j e PARESe '(j )(hi lo) 0

Faa hi = lolo = jEnd (Repita)


Exemplo Numrico Ilustrativo= + - + + -2 2 2 21 2 1 2( 11) ( 7)f x x x x


Exemplo Numrico Ilustrativo

[ ]T0 5 0x =-0

304( )

98f x

- = 0

00

0

( ) ( )

0,99580,0917

f xpf x

p

=- = -

p0


() = f(x0+p0)()

l() = 340 0,0305

(0) =340

'(0)= 305,29

aceitvel


Exemplo II

[ ]T1 2,5 1,5x =1

37( )

20f x

- = - 1

11

1

( ) ( )

0,87970,4755

f xpf x

p

=- =

p0

p1


() = f(x1+p1)()

l() = 15,625 0,0042

(0) =15,625'(0)= 42,060

aceitvel


Interpolao Quadrtica (0,10) Caso x0

()(0)=340 '(0)= 305,29 '(10)=161,797

1* = 5,31

21 121

( ) (0) '(0)( ) '(0) (0)q

2

* 1

1 1

'(0)2 ( ) (0) '(0)


Notas & Referncias Algoritmos que usam apenas valores de fk podem

ser ineficientes pois o mnimo precisa ser refinadoa um intervalo preciso Principais classes so dadas pelas mtodos da Seo urea e

de Fibonnaci Tipicamente armazenam trs pontos que determinam um

intervalo que contm um minimizador unidimensional

T. H. Cormen, C. E. Leisserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, 1990.

R. P. Brent, Algorithms for minimization without derivatives, Prentice Hall, Englewood Cliffs, N.J., 1973M. Bazaraa, H. Sherali, and C. Shetty, Nonlinear Programming, Theory and Applications.,JohnWiley & Sons, New York, second ed., 1993.

Referncias

OBRIGADO!

Prof. Erlon Cristian Finardi [email protected]

Documents

03 - Metodos de Busca Linear