Iteration of Complexity and Asymptotic Analysis of Gradient-Type Methods with Non-monotone Line Search on Riemannian Manifolds

Abstract This paper investigates gradient-type methods for solving optimization problems on Riemannian manifolds. In this approach, we utilize a search direction based on the gradient direction and employ a general non-monotone line search scheme to determine the stepsize at each iteration. This scheme encompasses several well-established non-monotone line search methods. Through our analysis, we demonstrate that this method exhibits asymptotic convergence characteristics and iteration-complexity bounds comparable to those of traditional Euclidean gradient-type methods using a non-monotone line search. The analysis presented significantly extends the study of gradient-type methods with line search to the domain of Riemannian manifolds, thereby providing several other line search options aiming at a better cost per iteration. Numerical experiments are also presented to illustrate the practical behavior of the proposed framework.