Topico 3d-MetodoQuaseNewton

Prévia do material em texto

OTIMIZAÇÃO 
Métodos de Direção de Busca 
Método de Quasi-Newton 
Ref.: Notas de aula do Prof. R. H. Takahashi 
Prof. Lenir Jr. - 2013 
Método de Newton Modificado 
 Garantir que o algoritmo produza diminuição monotônica da 
função objetivo, para funções não-lineares que não sejam 
quadráticas. 
 
Propostas de Correção 
 Cálculo corretivo estimativo da Hessiana de forma 
iterativa e dinâmica para atendimento de funções 
não-quadráticas. 
 Definir a construção gradativa de uma matriz Hk que 
corresponde a uma estimativa da inversa da 
Hessiana. 
 Métodos eficientes para tal fim são propostos, são 
eles:o método DFP (Davidon-Fletcher-Powell) e o 
metodo BFGS (Broyden-Fletcher-Goldfarb-Shanno), 
de forma geral, família de Broyden. 
Propostas de Correção 
 Correção proposta pelo método DFP: 
 
 
 Correção proposta pelo método BFGS 
 
 
 
 
 Correção de Broyden e correção inversa da hessiana 
Algoritmo Quasi-Newton 
 Definido a partir 
da família de 
Broyden, dado x0 
e α. 
Critérios de Parada e 
convergência 
Estabilização função objetivo 
Estabilização das variáveis de otimização 
Anulação do Vetor Gradiente 
Estabilização da Função Objetivo 
 Considera como estabilizado um algoritmo que varia, nas 
ultimas 5 iterações, menos de 0,1% da “amplitude” Δf da 
função objetivo, conforme fmax e fmin. 
Estabilização das Variáveis de 
Otimização 
 Considera como estabilizado um algoritmo cujo vetor de 
variáveis varia, nas últimas 5 iterações, menos de 0,1% da 
“faixa de variação” verificada do vetor de variáveis ao longo 
de toda a execução. 
Anulação do Vetor Gradiente 
 Se a função-objetivo é diferenciável, seu gradiente será nulo 
em seus pontos de mínimos locais. 
 A base de comparação adotada é o máximo valor da norma 
do gradiente ocorrido ao longo de toda a execução, denotado 
por Mmax. 
Exemplo 
 
Exemplo 
 Tabela de resultados com o uso do método do gradiente 
Exemplo - Convergência