Algorithms for Optimization on Manifolds Using Adaptive Cubic Regularization

Abstract

This thesis explores different techniques for solving the subproblem of the adaptive regularization with cubics (ARC) optimization algorithm, focusing on the Riemannian manifold setting. We give some background about optimization on manifolds and introduce the Riemannian ARC algorithm. In each iteration of ARC we require the minimization of a local cubic-regularized model of the objective function, and we look at convergence properties of various methods to approximate this minimum, including the Lanczos method, gradient descent, and nonlinear conjugate gradients. We prove a bound on the number of steps the Lanczos method requires in each subproblem to find an acceptable step, showing that the method cannot perform too badly in theory. Numerical experiments on a small set of benchmark problems seem promising, especially when using a nonlinear conjugate gradient subproblem solver.