Métodos de regularização cúbica com aproximações preguiçosas da hessiana

• Ano de defesa: 2025
• Autor(a) principal: Gehlen Filho, Vilmar
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal de Goiás; Instituto de Matemática e Estatística - IME (RMG); Brasil; UFG; Programa de Pós-graduação em Matemática (IME)
• Palavras-chave em Português: Método de regularização cúbica; Análise de complexidade; Hessiana preguiçosa; Otimização não-convexa; Cubic regularization method; Complexity analysis; Lazy hessian; Non- convex optimization; CIENCIAS EXATAS E DA TERRA::MATEMATICA
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tede/14032

Neste trabalho, apresentamos implementações de uma variante da Regularização Cúbica de Newton, incorporando aproximações preguiçosas da Hessiana para resolver problemas gerais de otimização não convexa (0-3). Nós propomos dois métodos: o primeiro (Algoritmo 1) utiliza de gradiente exato enquanto reutiliza a mesma aproximação da Hessiana para um bloco de $m$ iterações, por outro lado, o segundo (Algoritmo 2) estende essa ideia permitindo o uso de gradientes inexatos. Implementações de métodos, em que a informação sobre as derivadas são computadas por diferenças finitas são apresentadas. Um recurso interessante empregado pelos algoritmos é que ambos os parâmetros de regularização e a precisão das aproximações das derivadas (quando são atualizadas) são ajustadas usando um critério de busca linear não monótona. Estabelecemos complexidades de primeira ordem para ambos os métodos. Especificamente, dado uma precisão $\epsilon>0$, é mostrado que o Algoritmo~1 e o Algoritmo~2 requerem no máximo {$\mathcal{O}\left( m^{1/2} \epsilon^{-3/2}\right)$} iterações externas para gerar um ponto crítico $\epsilon$-aproximado do problema em questão. Quando as derivadas são computadas com aproximações por diferenças finitas, mostramos que o Algoritmo~1 (resp. Algoritmo~2) precisam no máximo {$\mathcal{O}\left((n+m)m^{-1/2}\epsilon^{-3/2}+(n+m)\right)$} (resp. {$\mathcal{O}\left((n^2+mn)m^{-1/2}\epsilon^{-3/2}+(n^2+mn)\right)$}) avaliações do gradiente e função (resp. função) para gerar um ponto crítico $\epsilon$-aproximado, onde $n$ é a dimensão do domínio da função objetivo.