Globalização do método de Newton

análise comparativa entre estratégias de buscas lineares em um método híbrido

Resumo

Neste trabalho, apresentamos um estudo de um método de Newton globalizado para determinar o minimizador de uma função objetivo f : Rn → R duas vezes continuamente diferenciável. O Método de Newton (MN) destaca-se por apresentar taxa de convergência superlinear, podendo chegar a quadrática, sob algumas hipóteses. Contudo, uma dificuldade do MN reside na exigência de um chute inicial próximo à solução. Para contornar essa dificuldade, pode-se empregar estratégias para o fornecimento de chutes iniciais mais adequados para o MN. Uma delas consiste em utilizar a direção de descida do gradiente da função objetivo. O método que utiliza essa direção de descida é conhecido como Método do Gradiente (MG) e é caracterizado pela convergência global da sequência gerada. Apesar disso, essa convergência tende a ser lenta com taxa linear, tornando-o menos eficiente. Buscando reunir a característica global do MG com as boas taxas de convergência do MN, consideramos um método que gera uma sequência com o emprego da direção de descida do gradiente. Este fornece um chute apropriado para as direções de descida dadas pelo MN. Essas direções são obtidas pelas soluções dk da equação linear H(xk)dk = −∇f(xk), onde H(xk) é a matriz Hessiana de f no ponto xk. Além da direção de descida, o estabelecimento de uma busca linear é fundamental na construção da sequência xk. Neste estudo, consideraremos as buscas monotônicas de Armijo, Goldstein e Wolfe. Estas serão testadas tanto na fase inicial conduzida pelo MG quanto na fase de aceleração promovida pelo MN. O objetivo é investigar o desempenho dessas combinações equipadas em um Método Híbrido (MH) ao determinar o mínimo global da função objetivo.