Riemannian trust-region algorithms

At x, build a model from the metric gradient g and a self-adjoint tangent operator H. The radius constrains the metric norm of η, not an unrelated ambient coordinate length. The candidate Rₓ(η) is feasible by construction. H may be the intrinsic Hessian, the pullback Hessian or a controlled approximation. For the intrinsic and pullback Hessians to agree away from criticality, a second-order retraction is sufficient. A general first-order retraction introduces the acceleration term discussed earlier and changes which second-order model is exact.

The predicted reduction is m(0)−m(η). It must be positive before forming the actual-to-predicted ratio. A large positive ratio indicates a useful prediction, while a small or negative ratio suggests a step or model that should not be trusted. Standard updates reject and shrink when the ratio is poor, accept when it exceeds a fixed positive threshold, and enlarge after a sufficiently good boundary step. Rejected iterations leave x unchanged while adjusting the radius. The exact thresholds and expansion/shrinkage factors are algorithmic parameters, not geometric identities.

Merely finding some vector inside the trust ball is not enough. A standard requirement is a fixed positive fraction of the decrease obtainable along the negative-gradient direction, called Cauchy decrease. A uniform bound on H then makes this decrease quantitatively useful. Truncated conjugate gradients can achieve it and terminate on a boundary or detected negative-curvature direction. Exact global solution of every tangent subproblem is unnecessary for first-order convergence, but an arbitrary early termination rule must still preserve the required decrease condition.

A sufficient regularity setting is a compact containing set of iterates, a lower-bounded C² objective and a smooth retraction on a uniform tangent neighborhood, with uniformly bounded self-adjoint models, exact model gradients and Cauchy-decrease steps. Cap all trial radii within that uniform neighborhood. The pullbacks then admit uniform local first-order Taylor bounds, and standard radius updates give the usual first-order convergence result. More general theorems state these bounds directly instead of assuming compactness. Quantitative complexity or fast local convergence requires further specified constants and approximation conditions; neither follows from the ratio formula alone.

At a critical point with a negative tangent-Hessian eigenvalue, a gradient-only Cauchy step is zero. It can therefore satisfy a first-order stopping condition at a saddle. Seeking approximate second-order stationarity additionally requires detecting or bounding negative curvature and obtaining corresponding model reduction. A Hessian approximation must be accurate enough for the claimed eigenvalue tolerance. These requirements are separate from gradient accuracy and from first-order global convergence; an implementation should report which criterion it actually certifies.

Near a nondegenerate minimum with positive-definite Hessian, accurate models and appropriately solved subproblems can recover fast Newton-like local convergence. That conclusion assumes more than feasibility or compactness, including sufficient objective smoothness and control of the retraction and Hessian approximation. The concrete circle examples below isolate model agreement without claiming a global rate: one checks a gradient-driven step, while the other starts at zero gradient and uses a negative-curvature direction. Both require comparing a model prediction with the actual selected retraction.