Método elipcêntrico: uma nova técnica de primeira ordem para minimização quadrática

Abstract

Este trabalho propõe e analisa um novo método de otimização de primeira ordem para minimizar funções quadráticas, denominado Método Elipcêntrico. A técnica fundamental explora a geometria das curvas de nível elipsoidais por meio de uma combinação de avaliações do gradiente, definindo o próximo iterando como o minimizador exato dentro de um subespaço bidimensional construído a partir de três pontos, uma generalização do conceito de centro de uma interpolação elíptica. A fundamentação teórica do trabalho aborda as teorias de convergência tanto do Método do Gradiente com busca exata quanto do novo Método Elipcêntrico para a classe das funções quadráticas estritamente convexas. Demonstramos que o passo elipcêntrico é pelo menos tão eficiente quanto o do Método do Gradiente, apresentando convergência global. No caso bidimensional R2, o método atinge o minimizador global em um único passo, coincidindo com o Método de Newton ou com o Método do Gradiente Conjugado. Embora em dimensões superiores não haja convergência finita, o método retém características newtonianas, exibindo uma taxa de convergência superior. Para validar a teoria e quantificar o desempenho prático, realizamos experimentos numéricos, implementando ambos os algoritmos, do Método Elipcêntrico e do Método do Gradiente, e os aplicamos a uma série de problemas com número de condicionamento κ variando de 2 a 243 e dimensões de R2 a R6, o método proposto se mostrou não apenas mais rápido, mas também numericamente mais robusto e preciso.