O Método Quasi-Newton

Ricardo Saboya de Toledo

Thales Eduardo Nazatto

Tópicos

• O Método de Newton.

• O Método Quasi-Newton.

• Algoritmos.

O Método de Newton• Tem como objetivo encontrar raízes de uma função.

• Também conhecido como Método de Newton-Raphson e possui casos especiais como o Método Babilônico.

• Baseado na aproximação da função com sua tangente, até chegar no seu limite.

• Fórmula geral:

O Método Quasi-Newton• Um dos defeitos do Método de Newton é que muitas das

aproximações dele são inconvenientes, tornando o custo computacional muito elevado.

• Com o método Quasi-Newton, a complexidade é reduzida de O(n2) para O(n2).

• É uma generalização do método da secante para sistemas não-lineares, gerando uma convergência superlinear:

O Método Quasi-Newton• É dado pela seguinte fórmula:

• Nele, a inversa da matriz Hessiana H (dada como B) é atualizada em toda iteração, desde que satisfaça a seguinte equação:

• O Δx satisfaz a seguinte equação:

Algoritmos• Davidon-Fletcher-Powell (DFP)

• Broyden-Fletcher-Goldfarb-Shanno (Broyden ou BFGS)

O Algoritmo DFP• Um dos mais antigos e inteligentes algoritmos para a geração da Hessiana

inversa foi originalmente proposto por Davidon (1959) e posteriormente desenvolvida por Fletcher e Powell (1963).

• Ela tem a interessante propriedade que, por um objetivo quadrático, gera simultaneamente as direções do conjugado gradiente enquanto gera a Hessiana inversa

• O método também é conhecido como o método da métrica variável (inicialmente sugerido por Davidon).

• Sua fórmula de atualização é:

Sendo qK = Hk+1 pK e Bk+1 qK = pK

O Algoritmo BFGS• A fórmula do BFGS é mais complicada do que a do DFP, mas simples de

aplicar.

• A fórmula de atualização do BFGS pode ser usada exatamente como a fórmula do DFP.

• Experimentos demonstraram que o desempenho do algoritmo BFGS é superior ao longo do algoritmo DFP. Assim, é muitas vezes preferido o algoritmo BFGS ao DFP.

• Sua fórmula de atualização é:

Sendo qK = Hk+1 pK e Bk+1 qK = pK

Algoritmos• Ambos os métodos têm propriedades que garantem uma rápida taxa de

convergência e convergência global sob certas condições.

• No entanto, eles poderiam falhar por problemas gerais não-lineares. Especificamente:

• O DFP é altamente sensível aos erros nas pesquisas lineares. • Ambos os métodos podem ficar presos em um ponto de sela. No método de Newton, um ponto de sela pode ser detectado durante modificações da (verdadeira) Hessiana. Portanto, é feita uma pesquisa ao redor do ponto final quando se utiliza métodos Quasi-Newton. • A atualização da Hessiana torna-se "corrompida" devido a imprecisões.

• Todo tipo de "truques", como o dimensionamento e pré-condicionamento existem para impulsionar o desempenho dos métodos.

Bibliografia• Numerical Analysis 7th edition, Richard L. Burden e J. Douglas Faires.

• Internet:

http://www.srl.gatech.edu/education/ME6103/

http://ricardo.ifas.ufl.edu/nonlinopt.workshop/

http://en.wikipedia.org/wiki/Quasi-Newton_method

http://en.wikipedia.org/wiki/Newton%27s_method