Why the line search terminates: brackets, cubics, and a guard

Every solver in this crate that follows a descent direction d from a point x reduces the problem to one dimension. Write the restriction of the objective along the ray as phi(a) = f(x + a d), so phi’(0) = g . d is negative for any descent direction. The line search’s job is to pick a step a that provably makes progress without spending the caller’s evaluation budget, and every claim below is about where those two guarantees come from.

1 The two Wolfe conditions

Sufficient decrease (Armijo) demands phi(a) <= phi(0) + c1 a phi’(0) with 0 < c1 < 1: the step must capture at least a c1 fraction of the decrease the initial slope promised. Because phi’(0) < 0 and a > 0, the right-hand side sits strictly below phi(0), so an accepted point is a real improvement, not a rounding story. That one-line consequence is the Lean theorem Rgmin.armijo_strict in proofs/lean/Rgmin/Zoom.lean.

The curvature condition demands abs(phi’(a)) <= c2 abs(phi’(0)) with c1 < c2 < 1: the slope must have flattened enough that the quasi-Newton update built from this step carries curvature information. Nocedal and Wright’s algorithms 3.5 and 3.6 (the bracket and the zoom) find a point satisfying both, and src/linesearch/zoom.rs is a direct implementation.

2 The bracket and the zoom

The outer loop (wolfe_search) expands a trial step until it either satisfies both conditions, overshoots (value above the Armijo line, or above the previous trial), or the slope turns nonnegative. Overshoot and slope-reversal both certify that a Wolfe point lies between the last two trials: that pair becomes the bracket [lo, hi], ordered so lo carries the lower value.

The zoom then shrinks the bracket. Each iteration proposes a trial inside [lo, hi], evaluates it, and replaces whichever end the Wolfe tests disqualify. The proposal is where the evaluation budget is won or lost, and the guard is where termination is proved.

3 The cubic Hermite proposal

At the two ends the zoom holds four numbers: phi(lo), phi’(lo), phi(hi), phi’(hi). There is exactly one cubic through both points with both slopes, and its interior minimizer has the closed form (Nocedal and Wright eq. 3.59)

d1 = phi’(lo) + phi’(hi) - 3 (phi(lo) - phi(hi)) / (lo - hi) d2 = sign(hi - lo) sqrt(d1²- phi’(lo) phi’(hi)) t = hi - (hi - lo) (phi’(hi) + d2 - d1) / (phi’(hi) - phi’(lo) + 2 d2)

On a well-behaved function the cubic model is third-order accurate, so t lands close to the true minimizer and the zoom converges in a handful of evaluations; the measured effect in anneal was 46 to 43 force calls per hop across the whole hopping battery, purely from this proposal replacing bisection. When the discriminant goes negative or a slope is non-finite the code falls back to the quadratic through phi(lo), phi’(lo), phi(hi), and below that to bisection: the ladder degrades in accuracy, never in safety.

4 The guard is the termination proof

A cubic through awkward data can propose a point arbitrarily close to either end, and a zoom that accepts such proposals can stall. The code clamps every proposal into the middle eighty percent of the bracket: no closer to an end than a tenth of the width. Two exact rational facts follow, proved in Zoom.lean:

• Rgmin.guarded_above / Rgmin.guarded_below: the clamp really does land in the interior band.

• Rgmin.zoom_shrinks: whichever end the trial replaces, the surviving bracket is at most 9/10 of the old width.

The width therefore decays geometrically (Rgmin.width_envelope is the bound, width_envelope_tendsto takes it to zero in the limit), and the evaluation budget of the zoom is logarithmic in the requested tolerance regardless of what the cubic does. The Rust test the_cubic_zoom_keeps_the_evaluation_budget in tests/lbfgs_state.rs holds the crate to that budget on a quadratic bowl.

5 What the accept layer adds

Above the line search, src/accept.rs offers three policies: take the clipped step (one oracle call), refuse any energy rise (Accept::Energy, up to ten halvings), or the Grippo-Lampariello-Lucidi nonmonotone window. The fallback steepest-descent probe inside the energy policies faces the same energy test as the step it replaces: a fallback that also fails reports the position unmoved, and the caller’s stall machinery owns what happens next. The test accept_energy_uphill_does_not_take_ten_steepest_retries pins the oracle count of that path.