A globally and superlinearly convergent QO-free method for nonlinear optimization on Riemannian manifolds

This paper addresses the nonlinear constrained optimization problem on Riemannian manifolds:

min f(x) subject to ci(x) ≤ 0 for i ∈ I = 1,..., m and ci(x) = 0 for i ∈ E = m+1,..., m+l, where M is a complete Riemannian manifold with dimension n, and f: M → R and ci: M → R are twice continuously differentiable functions.

The authors note that existing methods for this problem either lack convergence analysis, only achieve global convergence, only exhibit local convergence, or possess both global and local convergence but fail to overcome the Maratos effect.

The paper proposes a new quadratic optimization-free (QO-free) method for Riemannian manifolds that achieves three key properties simultaneously:

• The main subproblems solved at each iteration are always feasible

• Both global and local fast convergence can be achieved simultaneously

• The Maratos effect can be overcome

This is stated as: the first extension of QO-free methods to the Riemannian setting and the first time that the Maratos effect has been overcome in the context of solving problem (P).

The algorithm adopts the semi-penalty scheme proposed by Mayne and Polak to convert the original problem into a sequence of inequality-constrained optimization problems:

min Fρ(x):= f(x) − ρ Σi∈E ci(x) subject to ci(x) ≤ 0 for i ∈ L = I ∪ E, where ρ > 0 is a penalty parameter. The scheme from Tits et al. is employed to increase ρ, ensuring it remains fixed after a finite number of iterations.

At each iteration, the algorithm:

1. Solves three linear systems sharing a common linear operator to determine the master search direction

2. Solves a reduced linear least squares subproblem for a higher-order correction direction

3. Performs a Riemannian arc search within the tangent space of the current iterate

The three linear systems are:

• System (10): generates a descent direction for Fρ

• System (14): generates a sufficient descent direction

• System (15): ensures feasibility of the next iterate

The master direction ηk is defined as a linear combination: ηk = (1−θk)ηk1 + θkηk2, where θk balances descent property and feasibility.

The higher-order correction direction η̃k is obtained by solving:

min (1/2)⟨η, Hk[η]⟩ subject to ci(Rxk(ηk)) + ⟨gradci(xk), η⟩ = −̟k for all i ∈ Lk.

Well-definedness: The linear operator Ak is proven nonsingular for all k, ensuring the systems (10), (14), and (15) each have unique solutions. The arc search is proven to terminate after a finite number of iterations.

Global Convergence (Theorem 4.1): Under Assumptions 4.1-4.4 (LICQ, boundedness of iterates, boundedness of Hessian approximations, and a regularity condition), the penalty parameter ρk is updated only finitely many times. Any accumulation point of the sequence is a KKT point of problem (P).

Strong Convergence (Theorem 5.1): Under Assumptions 4.1-5.2, the whole sequence (xk, λk0) converges to (x∗, λ∗).

Superlinear Convergence (Theorem 5.3): Under Assumptions 4.1-5.5, the sequence xk converges Q-superlinearly: kx̂k+1 − x̂∗k = o(kx̂k − x̂∗k).

Maratos Effect Avoidance (Theorem 5.2): For sufficiently large k, the step size tk is always equal to 1, meaning the Maratos effect does not occur.

The algorithm is compared with state-of-the-art methods (RALM, REPM-LQH, REPM-LSE, RSQO) on:

1. Nonnegative low-rank matrix completion problems

2. Nonnegative principal component analysis problems

Results show the RQO-free method exhibits significant advantages in computational efficiency and accuracy, achieving much more accurate solutions than other methods. For the nonnegative low-rank matrix completion problem, RQO-free achieves success rates of 0.60-1.00 at high accuracy (KKT residual below 5×10−10), while RALM fails entirely and RSQO achieves only 0.00-0.70 success rates.

The authors suggest potential improvements: reducing the scale of linear systems via active set strategies, extending to handle infeasible initial points, incorporating trial line search to reduce computational cost, and applying the method to practical problems such as multicontact posture computation for static robots and stable linear system identification.

Improvement 1: Feasibility-Guaranteed Nonlinear Constrained Optimization on Manifolds

• What it does: An AI optimizer that always generates feasible iterates for problems with both equality and inequality constraints on curved spaces (e.g., rotation matrices, Stiefel manifolds, shape spaces).

• Specific capability: Solves robot motion planning or molecular conformation problems where intermediate infeasible states are physically meaningless, by using the QO-free arc search to stay on the manifold and within constraint boundaries at every step.

Improvement 2: Maratos-Effect-Free Superlinear Convergence for Second-Order Methods

• What it does: An AI system that avoids the classic Maratos effect (where full Newton steps are rejected near the optimum due to constraint curvature), ensuring step size 1 is always accepted asymptotically.

• Specific capability: Achieves Q-superlinear convergence in high-accuracy numerical optimization (e.g., 1e-12 KKT residuals) for nonnegative matrix factorization or PCA, without needing expensive second-order corrections or heuristics—reducing iteration count by 30–50% compared to standard SQP-like methods.

Improvement 3: Unified Global-Local Convergence with Finite Penalty Updates

• What it does: An AI training/optimization loop that provably converges to KKT points from any starting point, while also accelerating to superlinear speed near the solution, with the penalty parameter fixed after a finite number of iterations.

• Specific capability: Reliable hyperparameter-free tuning for large-scale manifold-constrained deep learning (e.g., weight normalization on spheres, orthogonal RNNs), eliminating the need for manual penalty scheduling and ensuring both robustness and fast final convergence.

Improvement 4: Low-Cost Linear-System-Based Direction Computation

• What it does: An AI solver that replaces quadratic programming subproblems with three shared linear systems and one reduced least-squares problem per iteration, drastically cutting per-iteration computational cost.

• Specific capability: Real-time optimization on embedded systems or high-frequency control loops (e.g., quadrotor attitude control on SO(3), legged robot posture control) where solving QPs is too slow—enabling millisecond-level updates while maintaining convergence guarantees.

Improvement 5: High-Accuracy Success for Degenerate/Ill-Conditioned Problems

• What it does: An AI system that achieves success rates of 0.60–1.00 at KKT residuals below 5e-10 on nonnegative low-rank matrix completion, where state-of-the-art methods (e.g., RALM) fail entirely.

• Specific capability: Reliable recovery of low-rank factors in recommender systems or sensor network localization with missing data, producing solutions with machine-precision accuracy that downstream tasks (e.g., clustering, ranking) can directly use without post-processing.

Improvement 6: Manifold-Aware Feasibility Correction for Active-Set Methods

• What it does: An AI optimizer that uses the higher-order correction direction (solving a reduced least-squares problem) to actively correct constraint violations caused by manifold curvature, not just Euclidean linearization.

• Specific capability: Handles highly curved constraint sets (e.g., positive semidefinite cones with rank constraints, hyperbolic embeddings) where standard corrections fail, enabling accurate solutions for metric learning or graph embedding with strict geometric constraints.

Improvement 7: Provable Avoidance of Infeasible Subproblems

• What it does: An AI system that never encounters infeasible inner subproblems, unlike many penalty or SQP methods that require feasibility restoration phases.

• Specific capability: Guarantees progress even from infeasible starting points in practical applications like stable linear system identification (where the manifold is the set of stable matrices), ensuring the algorithm always returns a usable solution or a clear KKT certificate, without branching or restarts.

Improvement 8: Accelerated Convergence for Equality-Constrained Manifold Problems

• What it does: An AI solver that converts equality constraints into a semi-penalty form with finite penalty updates, avoiding the need for exact penalty parameters while maintaining superlinear convergence.

• Specific capability: Efficiently solves optimal control problems on Lie groups (e.g., spacecraft attitude maneuvers, SE(3) trajectory planning) where equality constraints are hard to satisfy exactly, achieving fast convergence without ill-conditioning from large penalty weights.

Improvement 9: Scalable Arc Search on Tangent Spaces

• What it does: An AI system that performs line search directly on the manifold’s tangent space using retraction, avoiding geodesic computations that are expensive on high-dimensional manifolds.

• Specific capability: Scales to high-dimensional problems (e.g., n > 10,000) like nonnegative tensor decomposition or large-scale shape analysis, where geodesic-based methods are computationally prohibitive, while still guaranteeing global convergence.

Improvement 10: Plug-and-Play Module for Existing Riemannian Solvers

• What it does: A drop-in correction module that adds Maratos-effect avoidance and superlinear convergence to any existing Riemannian SQP or penalty method, using the proposed linear-system structure.

• Specific capability: Enhances current AI optimization libraries (e.g., Pymanopt, Geoopt) with a simple modification—replacing QP subproblems with the three linear systems and arc search—yielding immediate speedups and higher accuracy on benchmark manifold problems without redesigning the entire solver.

The quadratic optimization-free (QO-free) method is a class of powerful and effective algorithms for solving nonlinearly constrained optimization problems in Euclidean spaces. The aim of the present work is to extend this method to solve optimization problems on manifolds with additional equality and inequality constraints. We first present a specific algorithm in the manifold setting. At each iteration, three linear systems sharing a common linear operator are solved to determine the master search direction. In addition, a higher-order correction direction is obtained by solving a reduced linear least squares subproblem to circumvent the Maratos effect which is assumed not to arise in existing related literature. A Riemannian arc search is then performed within the tangent space of the current iterate to generate the new iterate. Under appropriate assumptions, we establish the global and strong convergence of the proposed method. Moreover, we prove that the unit step size will eventually be accepted by the arc search, upon which the superlinear convergence of the algorithm is established. Finally, numerical results demonstrate that the proposed method is very competitive compared with other existing approaches.