Riemannian Conjugate Gradient

A first-order method with superlinear convergence near the minimum, achieved by accumulating conjugate directions transported along the manifold.

Algorithm Summary

Algorithm

At each step, transport the previous conjugate direction to the current tangent space, then update via the chosen formula:

Fletcher-Reeves (globally convergent):

Polak-Ribière+ (clamped to ≥ 0; often faster in practice):

RCGConfig

pub struct RCGConfig {
    pub max_iters:    usize,      // default: 1000
    pub grad_tol:     f64,        // default: 1e-6
    pub init_step:    f64,        // default: 1.0
    pub armijo_c:     f64,        // default: 1e-4
    pub armijo_beta:  f64,        // default: 0.5
    pub max_ls_iters: usize,      // default: 50
    pub variant:       CgVariant,  // default: PolakRibiere
    pub restart_every: usize,     // default: 0 (never force restart; auto-restart still applies)
}

Code Examples

Minimize on S² with Polak-Ribière

use cartan::prelude::*;
use cartan::manifolds::Sphere;
use cartan_optim::{minimize_rcg, RCGConfig, CgVariant};
use nalgebra::SVector;
 
let s2 = Sphere::<3>;
let cost  = |p: &[f64; 3]| -p[0];
let rgrad = |p: &[f64; 3]| {
    s2.project_tangent(p, &SVector::from([-1.0, 0.0_f64, 0.0]))
};
 
let x0 = s2.project_point(&[-0.5_f64, 0.5, 0.707]);
let result = minimize_rcg(&s2, cost, rgrad, x0, &RCGConfig::default());
assert!(result.converged);

Switch to Fletcher-Reeves for non-smooth objective

let config = RCGConfig {
    variant: CgVariant::FletcherReeves,
    ..RCGConfig::default()
};
let result = minimize_rcg(&s2, cost, rgrad, x0, &config);

Numerical Notes

Variant selection: Polak-Ribière+ is the default and works well for most smooth problems. It clamps , so negative values trigger automatic restarts. Use Fletcher-Reeves if PR is unstable; it is globally convergent (no clamping needed).

Restart: automatic restart (reset to steepest descent) occurs when the conjugate direction is not a sufficient descent direction. restart_every: N forces a restart every N iterations regardless; useful for non-quadratic problems to prevent direction corruption.

Transport cost: ParallelTransport is called once per iteration. On manifolds with expensive transport (e.g., with large ), the overhead may not justify the CG benefit; profile before committing to RCG over RGD.