Local near-quadratic convergence of Riemannian interior point methods

2025/05/26 by Mitsuaki Obara, Obara, Mitsuaki, Takayuki Okuno +3
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Iterative Methods for Nonlinear Equations #Matrix Theory and Algorithms #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2505.19724

openalex publication_date 2025/05/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider Riemannian optimization problems with inequality and equality constraints and analyze a class of Riemannian interior point methods for solving them. The algorithm of interest consists of outer and inner iterations. We show that, under standard assumptions, the algorithm achieves local superlinear convergence by solving a linear system at each outer iteration, removing the need for further computations in the inner iterations. We also provide a specific update for the barrier parameter that achieves local near-quadratic convergence of the algorithm. We apply our results to the method proposed by Obara, Okuno, and Takeda (2026) and show its local superlinear and near-quadratic convergence with an analysis of the second-order stationarity. To our knowledge, this is the first algorithm for constrained optimization on Riemannian manifolds that achieves both local convergence and global convergence to a second-order stationary point. Numerical results support the theoretical analyses of the proposed methods.

Citations

• A primal-dual interior point trust region method for second-order stationary points of Riemannian inequality-constrained optimization problems
• Fast convergence of trust-regions for non-isolated minima via analysis of CG on indefinite matrices
• Constraint qualifications and strong global convergence properties of an augmented Lagrangian method on Riemannian manifolds
• Optimization on product manifolds under a preconditioned metric
• Riemannian Interior Point Methods for Constrained Optimization on Manifolds
• Sequential optimality conditions for nonlinear optimization on Riemannian manifolds and a globally convergent augmented Lagrangian method
• Stable Linear System Identification with Prior Knowledge by Riemannian Sequential Quadratic Optimization
• Sequential Quadratic Optimization for Nonlinear Optimization Problems on Riemannian Manifolds
• Nonnegative Low Rank Matrix Approximation for Nonnegative Matrices
• Calculating Optimistic Likelihoods Using (Geodesically) Convex Optimization
• Optimization on flag manifolds
• Simple algorithms for optimization on Riemannian manifolds with constraints
• A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs
• On Geodesically Convex Formulations for the Brascamp-Lieb Constant
• Riemannian optimal model reduction of stable linear systems
• On the superlinear convergence of Newton's method on Riemannian manifolds
• A Riemannian symmetric rank-one trust-region method
• A Geometric Approach to Low-Rank Matrix Completion
• On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming
• Interior Methods for Nonlinear Optimization
• Effects of Finite-Precision Arithmetic on Interior-Point Methods for Nonlinear Programming

Related

• A primal-dual interior point trust region method for second-order stationary points of Riemannian inequality-constrained optimization problems
• Analysis of Sequential Quadratic Programming through the Lens of Riemannian Optimization
• Sequential Quadratic Optimization for Nonlinear Optimization Problems on Riemannian Manifolds
• Simple algorithms for optimization on Riemannian manifolds with constraints
• Constraint qualifications and strong global convergence properties of an augmented Lagrangian method on Riemannian manifolds