Comparação numérica entre os métodos do gradiente ponderado com atraso e resíduos conjugados

Resumo

Neste trabalho, estamos interessados em resolver o seguinte problema de otimização convexa: min x∈Rn f(x) = 1/2 xTAx− bTx, onde A ∈ Rn×n é uma matriz simétrica e definida positiva e b ∈ Rn. Sabemos que resolver tal problema corresponde a encontrar a solução do sistema linear Ax = b. Ao longo dos anos, diversos métodos foram desenvolvidos, entre eles alguns diretos; i.e., métodos que nos fornecem a solução exata (a menos de erros de arredondamento) em um certo número fixo de operações, e os métodos iterativos os quais focamos nesse trabalho. Os métodos iterativos consistem em gerar uma sequência que aproxima a solução. Quando há muitas variáveis, aplicar métodos diretos pode ser inviável dado que tais métodos demandam memória considerável e têm custo computacional significativo. Em contrapartida, métodos iterativos são menos custosos, mesmo que a solução encontrada não seja a exata, mas sim uma aproximação seguindo alguma medida viável. Talvez o método iterativo mais famoso, e muito utilizado na prática, é o de Gradientes Conjugados (GC) devido a sua robustez e convergência finita. Em 2019, Leon propôs o chamado Método do Gradiente ponderado com atraso (do inglês, DWGM), que se mostrou superior ao GC em testes computacionais no que diz respeito ao número de iterações e tempo computacional, ainda que tenha um custo por iteração ligeiramente maior. Outras análises foram realizadas considerando essa competitividade, como, por exemplo, o estudo das propriedades das sequências geradas pelo DWGM, extensão para funções fortemente convexas e uma generalização que acomoda toda uma família de métodos, desde o GC até o DWGM. Outro método da mesma classe do GC (i.e., baseado em direções conjugadas) é o de Resíduos Conjugados (RC), menos discutido na literatura, mas com bons resultados teóricos e desempenho similar ao GC.