Topico 3c-MetodoNewton

Prévia do material em texto

OTIMIZAÇÃO 
Métodos de Direção de Busca 
Método de Newton 
Ref.: Notas de aula do Prof. R. H. Takahashi 
Prof. Lenir Jr. - 2013 
Definições Importantes 
 
Definições Importantes 
 Gradiente 
 
 Gradiente e Hessiana para 3 variáveis 
 
 
 
 Forma geral para Hessiana 
Aproximações Quadráticas 
 Suponha-se agora que, conhecendo-se a priori a 
natureza da função objetivo; 
 Razoável admitir que essa função corresponda, de 
maneira aproximada, a uma função quadrática, 
dentro de algum domínio que contenha o ponto de 
mínimo x*. 
 A aproximação e feita ao redor de um ponto xo, 
também contido nesse domínio e expressa numa 
série de Taylor. 
Aproximações Quadráticas 
 
 
 
 
 
 
Aproximações Quadráticas 
 Ou seja, se a função a ser otimizada for exatamente 
quadrática, basta se conhecer o gradiente e a 
Hessiana em um ponto qualquer xo; 
 Em uma única iteração, então , determinar o ponto 
de mínimo x*, através da equação (6.14). 
 A equação (6.14) pode ainda ser empregada para 
produzir estimativas do ponto de mínimo que 
convergem muito mais rapidamente que aquelas 
produzidas pelo Algoritmo do Gradiente. 
Aproximações Quadráticas 
 
 
Aproximações Quadráticas 
 O que isto quer dizer? 
Conforme Eq. 6.11 
Algoritmo de Newton 
 
Algoritmo de Newton 
 Funções com forma precisamente quadrática, o 
algoritmo converge para a solução exata do problema, 
de maneira não-iterativa, em um único passo. 
 Entretanto a situação geral é: as funções a serem 
otimizadas, embora em sua maioria sejam duas 
vezes diferenciáveis, o que é necessário para a 
aplicabilidade desse método, entretanto na maioria 
dos casos não serão quadráticas. 
 O Algoritmo de Newton, na formulação apresentada, 
pode até mesmo não convergir. 
Algoritmo de Newton 
 Observando os requisitos arrolados entre as 
hipóteses do teorema da convergência global, 
verifica-se que o Algoritmo de Newton não 
satisfaz a exigência de que a iteração deva ser 
descendente. 
 Ou seja, que o valor da função objetivo 
necessariamente decresça a cada iteração. 
 Nada garante que o cálculo analítico da solução que 
seria a exata para um problema quadrático, se aplicado 
a um problema que não é quadrático, pode levar até 
mesmo a um aumento no valor da função objetivo. 
 
Algoritmo de Newton 
 Exercício: Mostre a execução do algoritmo de 
busca pelo método de Newton na função: 
 
𝑓 𝑋 = (𝑥1−3)
2 + (𝑥2 − 2)
2 
 
 
 para X0 = [3/4 1/4]’