Trust regions and the Steihaug boundary#

Line searches commit to a direction and haggle over the length. Trust regions invert the deal: fix a budget on the length, then ask for the best step the local model affords inside it. This page derives the machinery behind src/trust.rs (dense dogleg) and src/hvp.rs (matrix-free Steihaug-Toint), and names the exact rational facts the Lean proofs pin.

1 The model and the ratio#

Around the current point the quadratic model is

m(p) = f + g . p + (1/2) p . H p,

trusted only within norm(p) <= Delta. After solving the subproblem approximately for a step p, the honesty check compares the actual reduction to the predicted one:

rho = (f - f(x + p)) / (m(0) - m(p)).

The radius update (Nocedal-Wright algorithm 4.1, update_radius) shrinks by four when rho < 1/4, doubles (capped) when rho > 3/4 and the step pressed the boundary, and otherwise holds. Three properties make this loop honest, each proved in proofs/lean/Rgmin/Trust.lean:

  • shrink_ge_floor / shrink_pos: the radius never leaves the positive floor, so no division or comparison downstream degenerates.

  • shrink_strict and the collapse recursion: consecutive failures decay the radius geometrically (one factor of four per rejection), so the loop must either accept a step or hit the floor in finitely many rejections – at which point minimize_newton_cg returns the TrustCollapsed error instead of reporting convergence it does not have.

  • rejection_propagates: with a positive predicted reduction, a step that failed to lower the objective has rho <= 0 < eta and cannot be accepted. The acceptance test cannot be talked into an uphill step by a large denominator.

2 Steihaug-Toint: conjugate gradients under a leash#

For large n the dense subproblem solve is the whole bill, so the matrix-free path never forms H: it runs conjugate gradients on H p = -g, spending one Hessian action per iteration, and stops early on any of three events.

  1. Small residual: the inexact-Newton forcing sequence rtol = min(sqrt(norm(g)), 1/2) keeps early outer iterations cheap and the tail superlinear (Nocedal-Wright eq. 7.3).

  2. Negative curvature: if d . H d <= 0 the model is unbounded along d, and the right amount of greed is to walk the ray to the trust boundary. Rgmin.ray_further_is_lower in Steihaug.lean proves the model is nonincreasing along such a ray, so the boundary point minimizes the model on it.

  3. Boundary crossing: if the next iterate would leave the region, the code solves for the exact crossing.

The crossing length tau is the positive root of

dd tau2+ 2 zd tau + (zz - r2) = 0,

where zz, zd, dd are the tracked inner products of the current iterate and direction. With the discriminant named as a square (s2= zd2+ dd (r2- zz)), two exact rational facts close the construction, both in Steihaug.lean:

  • boundary_on_sphere: the root lands exactly on the sphere, norm(z + tau d)2= r2, in whichever inner product the caller tracked – the same algebra serves the Euclidean and preconditioned runs.

  • boundary_tau_nonneg: inside the region the root is nonnegative; a boundary exit extends the step, never retracts it.

The Rust test negative_curvature_walks_to_the_trust_boundary pins the implemented step to the sphere at 1e-10 on an indefinite model.

3 The metric bookkeeping under a preconditioner#

steihaug_pcg runs the same loop under a preconditioner M, and the trust boundary lives in the M-norm. The Conn-Gould-Toint recurrences track p.Mp, p.Md, d.Md from quantities already on hand (with M z = r, every needed product reduces to Euclidean dots), so norms cost no extra applications of M. Rgmin.metric_update_scales in Precond.lean pins the linearity that makes the tracked comparison scale-consistent, and the Rust test the_preconditioned_boundary_lives_in_the_sketch_metric holds the identity-preconditioner run bit-equal to the plain one.

4 Dogleg, for when the Hessian is cheap#

When a dense Hessian is affordable (HessianObjective), the dogleg path (dogleg_direction) interpolates between the Cauchy point (the model minimizer along -g) and the Newton point, taking whichever the radius allows. It is the classical picture the Steihaug path generalizes: CG’s first iterate is the Cauchy step, its limit is the Newton step, and truncation by the boundary lands in between.