Riemannian Gradient Descent

The simplest first-order Riemannian optimizer. At each step, retract along the negative Riemannian gradient with an Armijo backtracking line search.

Algorithm Summary

Property	Value
Function	`minimize_rgd`
Config	`RGDConfig`
Trait requirements	`Manifold + Retraction`
Convergence	(general); global for geodesically convex
Line search	Armijo backtracking

Algorithm

where satisfies the Armijo condition:

with , by default.

`RGDConfig`

pub struct RGDConfig {
    pub max_iters:    usize,  // default: 1000
    pub grad_tol:     f64,    // default: 1e-6 - stop when ||grad|| < grad_tol
    pub init_step:    f64,    // default: 1.0  - initial Armijo step size
    pub armijo_c:     f64,    // default: 1e-4 - sufficient decrease constant
    pub armijo_beta:  f64,    // default: 0.5  - backtracking factor
    pub max_ls_iters: usize,  // default: 50   - max line search steps
}

Code Examples

Minimize on S²

use cartan::prelude::*;
use cartan::manifolds::Sphere;
use cartan_optim::{minimize_rgd, RGDConfig};
use nalgebra::SVector;
 
let s2 = Sphere::<3>;
 
// f(p) = -p[0]: minimum at north pole [1, 0, 0]
let cost  = |p: &[f64; 3]| -p[0];
let rgrad = |p: &[f64; 3]| {
    let eg = SVector::from([-1.0, 0.0_f64, 0.0]);
    s2.project_tangent(p, &eg)
};
 
let x0 = [-0.5_f64, 0.5, 0.707];
let x0 = s2.project_point(&x0);
 
let result = minimize_rgd(&s2, cost, rgrad, x0, &RGDConfig::default());
assert!(result.converged);
assert!((result.point[0] - 1.0).abs() < 1e-5);

Custom config: more aggressive backtracking

let config = RGDConfig {
    max_iters: 500,
    grad_tol: 1e-8,
    armijo_beta: 0.3,   // more aggressive backtracking
    ..RGDConfig::default()
};
let result = minimize_rgd(&s2, cost, rgrad, x0, &config);

Numerical Notes

Riemannian gradient: the rgrad closure must return the Riemannian gradient (projected onto the tangent space), not the Euclidean gradient. Use manifold.project_tangent(p, &euclidean_grad) to project.

Step size: if the algorithm does not converge, try reducing init_step or increasing max_ls_iters. A starting step of is often safer on curved manifolds with small injectivity radii.

converged = false: check grad_norm; if it is small but max_iters was hit, simply increase max_iters.

Applications

Initial pass before switching to RCG or RTR
Non-smooth or poorly conditioned objectives where CG restarts dominate
Feasibility problems on manifolds