A Primal-Dual Interior Point Trust Region Method for Second-Order Stationary Points of Riemannian Inequality-Constrained Optimization Problems
TL;DR
To the best of the knowledge, this is the first algorithm that incorporates the trust region strategy for constrained optimization on Riemannian manifolds and has the second-order convergence property for optimization problems on Riemannian manifolds with nonlinear inequality constraints.
Abstract
Abstract. We consider Riemannian inequality-constrained optimization problems. Such problems inherit the benefits of Riemannian approach developed in the unconstrained setting and naturally arise from applications in control, machine learning, and other fields. We propose a Riemannian primal-dual interior point trust region method (RIPTRM) for solving them. We prove its global convergence to an approximate Karush–Kuhn–Tucker point and a weak second-order stationary point. Under the strict complementarity condition, this result reduces to global convergence to a second-order stationary point. To the best of our knowledge, this is the first algorithm that incorporates the trust region strategy for constrained optimization on Riemannian manifolds and has the second-order convergence property for optimization problems on Riemannian manifolds with nonlinear inequality constraints. We conduct numerical experiments in which we introduce a truncated conjugate gradient method and an eigenvalue-based subsolver for RIPTRM to approximately and exactly solve the trust region subproblems, respectively. Empirical results show that RIPTRMs consistently find solutions with high accuracy.