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
Tcnicas para a Operao de SEE 33EEL6000 Mtodos Numricos de Otimizao
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)
Tcnicas para a Operao de SEE 44EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 55EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 66EEL6000 Mtodos Numricos de Otimizao
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)
Tcnicas para a Operao de SEE 77EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 88EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 99EEL6000 Mtodos Numricos de Otimizao
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)
Tcnicas para a Operao de SEE 1010EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 1111EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 1212EEL6000 Mtodos Numricos de Otimizao
Dificuldades para Encontrar k( )k
kPrimeiro Ponto
Estacionrio
Primeiro Mnimo Local
Mnimo Global
( ) ( 0)k kf x f
Tcnicas para a Operao de SEE 1313EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 1414EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 1515EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 1616EEL6000 Mtodos Numricos de Otimizao
Condies de Wolfef(xk + pk) f(xk) + c1fkTpk e f(xk + pk)T pk c2fkTpk( ) ( )k kf x p
0
Tcnicas para a Operao de SEE 1717EEL6000 Mtodos Numricos de Otimizao
Condies (Fortes) de Wolfe
( ) ( )k kf x p
f(xk + pk) f(xk) + c1fkTpk e |f(xk + pk)T pk | c2 |fkTpk |
|c2'(0)|
Tcnicas para a Operao de SEE 1818EEL6000 Mtodos Numricos de Otimizao
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)
Tcnicas para a Operao de SEE 1919EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 2020EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 2121EEL6000 Mtodos Numricos de Otimizao
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
Tcnicas para a Operao de SEE 2222EEL6000 Mtodos Numricos de Otimizao
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)
Tcnicas para a Operao de SEE 2323EEL6000 Mtodos Numricos de Otimizao
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)
Tcnicas para a Operao de SEE 2424EEL6000 Mtodos Numricos de Otimizao
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)
Tcnicas para a Operao de SEE 2525EEL6000 Mtodos Numricos de Otimizao
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)
Tcnicas para a Operao de SEE 2626EEL6000 Mtodos Numricos de Otimizao
Exemplo Numrico Ilustrativo= + - + + -2 2 2 21 2 1 2( 11) ( 7)f x x x x
Tcnicas para a Operao de SEE 2727EEL6000 Mtodos Numricos de Otimizao
Exemplo Numrico Ilustrativo
[ ]T0 5 0x =-0
304( )
98f x
- = 0
00
0
( ) ( )
0,99580,0917
f xpf x
p
=- = -
p0
Tcnicas para a Operao de SEE 2828EEL6000 Mtodos Numricos de Otimizao
() = f(x0+p0)()
l() = 340 0,0305
(0) =340
'(0)= 305,29
aceitvel
Tcnicas para a Operao de SEE 2929EEL6000 Mtodos Numricos de Otimizao
Exemplo II
[ ]T1 2,5 1,5x =1
37( )
20f x
- = - 1
11
1
( ) ( )
0,87970,4755
f xpf x
p
=- =
p0
p1
Tcnicas para a Operao de SEE 3030EEL6000 Mtodos Numricos de Otimizao
() = f(x1+p1)()
l() = 15,625 0,0042
(0) =15,625'(0)= 42,060
aceitvel
Tcnicas para a Operao de SEE 3131EEL6000 Mtodos Numricos de Otimizao
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)
Tcnicas para a Operao de SEE 3232EEL6000 Mtodos Numricos de Otimizao
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]
Recommended