Optimizers

This chapter documents what the three optimizers in src/optimizer/ actually do — the equations as implemented, the defaults as coded, and the deviations from textbook forms with the reason the code gives for each. Every formula names the module it comes from.

The problem all three solve

Given residual blocks $r_i$ over manifold variables, Problem defines

$$\underset{x}{\min }f(x)=\frac{1}{2}\Vert r(x){\Vert }_2^2=\frac{1}{2}\sum _i\Vert r_i(x){\Vert }^2$$

Variables live on manifolds, so the step is applied with $⊞$ rather than addition: $x\leftarrow x⊞h$, with the per-group right-plus from apex-manifolds. The Jacobian $J$ is therefore taken with respect to the tangent space, and every matrix below has tangent dimension, not parameter dimension. An SE3 variable contributes 6 columns, not 7.

Two quantities recur:

$$g=J^{\mathsf{T}}r\text{(gradient)},H\approx J^{\mathsf{T}}J\text{(Gauss-Newton Hessian)}$$

H drops the ${\sum }_i{r}_i{\nabla }^2{r}_i$ term of the true Hessian, which is the Gauss-Newton approximation and is accurate when residuals are small or nearly linear (gauss_newton.rs).

Sign convention. LinearSolver::get_gradient returns $+J^{\mathsf{T}}r$, not the right-hand side $-J^{\mathsf{T}}r$ (linalg/mod.rs). Each optimizer negates it before forming the linear system. tests/linear_solver_contract.rs pins this for every backend, because getting it backwards produces a step that ascends.

Gauss-Newton

optimizer/gauss_newton.rs. Solves the normal equations exactly and takes the full step, with no step-size control at all (gauss_newton.rs):

$$(J^{\mathsf{T}}J)h=-J^{\mathsf{T}}r,x\leftarrow x⊞h$$

There is no damping, no trust region, and no line search. Convergence is quadratic near a solution where the Gauss-Newton approximation holds, and the method diverges when started far away or when $J^{\mathsf{T}}J$ is ill-conditioned. Use it when you already know the problem is well-conditioned and the initial guess is close; otherwise use LM.

Options

The schur_* fields (schur_variant, schur_preconditioner, schur_cg_max_iterations, schur_cg_tolerance, schur_cg_q_tolerance) exist on all three configs and are forwarded to the linear solver — see Linear Solvers.

Levenberg–Marquardt

optimizer/levenberg_marquardt.rs. The default optimizer, and the one for_bundle_adjustment() presets.

The damped system

$$(J^{\mathsf{T}}J+\lambda D)h=-J^{\mathsf{T}}r$$

D is not the identity. It is the clamped diagonal of the Hessian (linalg/mod.rs):

$$D_{jj}=\mathrm{clamp}((J^{\mathsf{T}}J{)}_{jj},d_{\min },d_{\max }),d_{\min }=10^{-6},d_{\max }=10^{32}$$

This is Ceres’s LevenbergMarquardtStrategy: damping each column in proportion to its own curvature makes the step invariant to a rescaling of the parameters, which uniform $\lambda I$ is not. Damping::identity sets $d_{\min }=d_{\max }=1$ and recovers plain $\lambda I$ exactly.

The lower clamp matters: without it a column with no curvature would receive no damping at all, leaving that direction unconstrained.

Step quality

After solving, the step is scored by the gain ratio. Predicted reduction comes from the quadratic model (optimizer/mod.rs):

$${\Delta }_{\text{pred}}=-h^{\mathsf{T}}g-\frac{1}{2}{h}^{\mathsf{T}}Hh$$

evaluated with the un-damped $H$ — hessian_vec_product is documented to never carry $\lambda D$, because damping in the model would corrupt $\rho$ (linalg/mod.rs). Then (optimizer/mod.rs):

$$\rho =\frac{f(x)-f(x⊞h)}{{\Delta }_{\text{pred}}}$$

with two guards the textbook ratio does not have:

• ${\Delta }_{\text{pred}}<-10^{-15}$ → $\rho =-1$. A negative predicted reduction means the model says the step increases cost, so it is rejected outright rather than producing a misleading positive ratio.
• $|{\Delta }_{\text{pred}}|\le 10^{-15}$ → $\rho =1$ if the actual reduction was positive, else $0$.

The step is accepted when $\rho >$min_relative_decrease, default 1e-3 (levenberg_marquardt.rs), matching Ceres. This is not the textbook $\rho >0$.

Damping update — two rules

Selected by damping_update (levenberg_marquardt.rs).

Nielsen (default, what Ceres uses). On an accepted step:

$$\lambda \leftarrow \lambda \cdot \max \left(\frac{1}{3},1-(2\rho -1{)}^3\right),\nu \leftarrow {\nu }_0$$

On a rejected step $\lambda \leftarrow \lambda \nu$ and $\nu \leftarrow 2\nu$, so consecutive failures escalate geometrically. Reads damping_nu; ignores damping_increase_factor, damping_decrease_factor, min_step_quality, good_step_quality.

Marquardt. Three bands:

$$\lambda \leftarrow \{\begin{array}{ll}\lambda \cdot \text{decrease}& \rho \ge \text{good\_step\_quality}\\ & \\ \lambda \cdot \text{increase}& \rho \le \text{min\_step\_quality}\text{or rejected}\\ & \\ \lambda & \text{otherwise}\end{array}$$

A rejected step always increases $\lambda$ whatever $\rho$ was — the code notes that leaving it unchanged would recompute the identical step next iteration and stall (levenberg_marquardt.rs). Afterwards $\lambda$ is clamped to [damping_min, damping_max].

Options

Note the scaling default differs between optimizers: LM defaults to false, Dog Leg to true. Enable it for LM on mixed-scale problems solved with Cholesky or QR.

for_bundle_adjustment() preset

levenberg_marquardt.rs overrides: ImplicitSparseSchur linear solver, SchurJacobi preconditioner, λ₀ = 1e-3 (the plain default is 1e-4), max_iterations = 20, cost_tolerance = 1e-6, parameter_tolerance = 1e-8, gradient_tolerance = 1e-10. The solver choice is justified by the measured table in that comment; see Benchmarks.

Dog Leg

optimizer/dog_leg.rs. Powell’s dog leg over a spherical trust region of radius $\Delta$, interpolating between the steepest-descent and Gauss-Newton directions.

Cauchy point

The unconstrained minimiser along $-g$ (dog_leg.rs):

$$\alpha =\frac{g^{\mathsf{T}}g}{g^{\mathsf{T}}Hg},p_c=-\alpha g$$

with a guard: if $|g^{\mathsf{T}}Hg|\le 10^{-15}$ then $\alpha =1$.

Step selection — three cases

From dog_leg.rs, given $\Delta$:

Case 1 — GN step fits. If $\Vert h_{gn}\Vert \le \Delta$, take $h=h_{gn}$ (StepType::GaussNewton).

Case 2 — Cauchy point already outside. If $\Vert p_c\Vert \ge \Delta$, take the steepest-descent direction scaled to the boundary (StepType::SteepestDescent):

$$h=\frac{\Delta }{\Vert d_{sd}\Vert }{d}_{sd}$$

Case 3 — interpolate. Otherwise walk from $p_c$ toward $h_{gn}$ to the boundary. With $v=h_{gn}-p_c$, solve $\Vert p_c+\beta v{\Vert }^2={\Delta }^2$, i.e. $a{\beta }^2+2b\beta +c=0$ with

$$a=v^{\mathsf{T}}v,b=p_c^{\mathsf{T}}v,c=\Vert p_c{\Vert }^2-{\Delta }^2$$

The implementation does not use the textbook quadratic root. It uses Ceres’s cancellation-avoiding branch (dog_leg.rs), with $d^2=b^2-ac$:

$$\beta =\{\begin{array}{ll}\frac{-b+d}{a}& b\le 0\\ & \\ \frac{-c}{b+d}& b>0\end{array}$$

Choosing by the sign of $b$ avoids catastrophic cancellation in the subtraction. Fallbacks: $\beta =1$ when $d^2<0$ (geometrically impossible, handled anyway) or $|a|<10^{-15}$ (degenerate $v$). Finally $\beta$ is clamped to $[0,1]$ and $h=p_c+\beta v$ (StepType::DogLeg).

Trust-region update

dog_leg.rs. Growth is Ceres’s rule, not a fixed doubling:

$$\Delta \leftarrow \min ({\Delta }_{\max },\max (\Delta ,3\Vert h\Vert ))\text{when }\rho >\text{good\_step\_quality}$$

$$\Delta \leftarrow \max ({\Delta }_{\min },\frac{1}{2}\Delta )\text{when }\rho <\text{poor\_step\_quality}$$

and $\Delta$ is left unchanged in between.

$\Vert h\Vert$ is measured in the scaled space when Jacobi scaling is on — which is Dog Leg’s default. The code documents why: the radius bounds the scaled step, so feeding the un-scaled norm would compare two different units and grow $\Delta$ by an arbitrary factor (dog_leg.rs).

Step reuse

On a rejected step Dog Leg caches the GN step, Cauchy point, gradient and $\alpha$, and reuses them next iteration (dog_leg.rs). Only $\Delta$ changed, so the expensive linear solve does not have to be redone. The cache is invalidated on any accepted step, because the parameters moved. Controlled by enable_step_reuse (default true).

Options

Jacobi column scaling

When use_jacobi_scaling is on, columns are equilibrated before the solve (optimizer/mod.rs):

$$S_{jj}=\frac{1}{1+\Vert J_{:,j}{\Vert }_2},\tilde{J}=JS$$

The solve happens in the scaled space and the step is mapped back with $h=S\tilde{h}$. The $1+$ in the denominator keeps the scaling finite for a structurally empty column.

Ordering matters and the code is explicit about it: the predicted reduction is computed before un-scaling (levenberg_marquardt.rs), because the solver’s cached gradient and Hessian are the scaled ones and all three vectors must live in the same space. The predicted reduction is a value of the quadratic model and is invariant under the change of variables, so it is equally valid for the un-scaled step.

Convergence criteria

All three optimizers share check_convergence (optimizer/mod.rs), evaluated in this order.

Always checked, before anything else:

1. InvalidNumericalValues — any of new cost, step norm or gradient norm is NaN or infinite.
2. Timeout — elapsed ≥ timeout.
3. MaxIterationsReached — iteration ≥ max_iterations.

Only after an accepted step (a rejected step cannot terminate the solve):

4. GradientToleranceReached — $\Vert g\Vert <{\epsilon }_g$.
5. From iteration 1 onward, ParameterToleranceReached: $\Vert h\Vert \le {\epsilon }_x(\Vert x\Vert +{\epsilon }_x)$ — a relative test, so it scales with the parameter magnitude.
6. From iteration 1 onward, CostToleranceReached: $|f_k-f_{k+1}|/\max (f_k,10^{-10})<{\epsilon }_f$.
7. MinCostThresholdReached — optional $f<\tau$ cutoff.
8. TrustRegionRadiusTooSmall — LM and Dog Leg only.

LM additionally reports StalledNoProgress after max_consecutive_rejected_steps consecutive rejections (levenberg_marquardt.rs): damping has grown until every trial step is negligible, so the remaining budget cannot change the cost.

Output

All three return SolverResult<T> (optimizer/mod.rs):

Note that several statuses are successful terminations, not failures: Converged, CostToleranceReached, GradientToleranceReached, ParameterToleranceReached and StalledNoProgress are all treated as converged by the benchmark harness. MaxIterationsReached means the budget ran out with the solve still improving.