Adaptive trust-region and riemannian gradient descent methods without function evaluations

Abstract

Resumo: Neste trabalho propomos dois algoritmos de otimização irrestrita. O primeiro é um método de região de confiança, onde o raio de confiança e da forma d_(k)||grad f (x_(k))|| e d_(k) pode reduzir ou aumentar a cada iteração, dependendo de quanto o passo reduziu a norma do gradiente. A principal inspiração é o método WNGrad [48]. Nos testes numéricos vemos uma competitividade com outros métodos, incluindo o método de região de confiança padrão. O segundo método apresentado e um método de descida por gradiente em contexto Riemanniano, com passo -t_(k)grad f(x_(k)), onde t_(k) tem uma atualização similar ao d_(k). Nos experimentos numéricos os resultados apontam para um bom desempenho do método comparado com a busca de Armijo. Em ambos os métodos podemos dividir em dois casos, um conservativo, levando no máximo O(e^-2) iteracões para atingir um ponto estacionário com precisão e e um flexível, levando no máximo O(|log(e)|e^-2) iteraçães para atingir um ponto estacionário com precisão e, com e > 0.

Abstract: In this work we proposed two algorithms of unconstrained optimization. The first one is a trust-region method, where the trust radius is given by d_(k)||grad f (x_(k))|| and d_(k) is a sequence updated in each step. The behaviour of d_(k) is inspired in the reciprocal of d_(k) from the WNGrad method [48], but with the difference that d_(k) may not be monotonically decreasing like the reciprocal of d_(k). In the numerical tests we can see that the proposed method is competitive with other methods, including the standard trust-region method. The second presented algorithm is a gradient descent method in the Riemannian context, with step -t_(k)grad f (x_(k)), where t_(k) have an update similar to d_(k). In the numerical experiments, the results indicate to a better performance compared with the Armijo’s linesearch. In both methods we can split in two cases, a conservative version taking at most O(e^-2) iterations to find an e-stationary point and a flexible version taking at most O(|log(e)|e^-2) iterations to find e-stationary point, with e > 0.