Accept step s using a verifiable decrease rule

Try

At x=2 for f(x)=x², choose the negative-gradient direction d=−4. A full step lands at−2 and gives no objective reduction. Halving the step lands at zero and solves the problem. Backtracking formalizes this trial-and-reduction process. It tests a sufficient-decrease inequality rather than accepting any numerical change that happens to be negative. The direction and the step are separate choices: line search determines how far to move along an already selected direction.

Predict

Predict whether backtracking must succeed for every direction. If ∇f(x)·d is positive, the direction initially increases the function, so the standard descent proof is unavailable. With a strict descent direction and differentiability, sufficiently small positive steps satisfy Armijo decrease. This is a local existence statement. To derive convergence over infinitely many iterations, we will also need uniform control preventing accepted steps from becoming arbitrarily tiny for unrelated reasons.

Experiment

Use Armijo parameter c=1/4 at the opening point. The right side is f(x)+cα∇f(x)·d=4−4α. Compare it with the actual trial value.

Trial α	New point	Actual f	Armijo bound	Accepted?
1	−2	4	0	No
1/2	0	0	2	Yes

Now choose d=+4 and explain why the usual sufficient-small-step argument fails. The slope is positive, so the linear term itself points the wrong way. A line-search routine should not silently assume that a Newton or approximate direction is descent; that property must be checked or guaranteed by its construction.

Understand

Armijo requires f(x+αd)≤f(x)+cα∇f(x)·d with 0<c<1. Differentiability gives f(x+αd)=f(x)+α∇f(x)·d+o(α). For a strict descent direction, the unused fraction (1−c) of the negative slope provides a margin that eventually dominates the remainder. Thus repeated multiplication of the trial step by a fixed factor β in (0,1) terminates after finitely many reductions at a nonstationary point.

For d=−∇f and an L-Lipschitz gradient, the descent lemma guarantees Armijo whenever α≤2(1−c)/L. With a fixed initial trial step and fixed β, the accepted step is therefore bounded below by a positive constant depending on these quantities. If f is bounded below and the smoothness bound holds throughout the relevant region, summing Armijo decreases forces the gradient norms to zero. The uniform step bound is essential to this argument; arbitrary diminishing steps can produce a finite total movement before reaching stationarity.

Apply

The weak Wolfe curvature condition additionally requires ∇f(x+αd)·d≥c₂∇f(x)·d, where the Armijo parameter c₁ satisfies 0<c₁<c₂<1. Because the original slope is negative, this asks for enough slope improvement and prevents accepting a very short step solely because it gives a tiny decrease. It is not guaranteed by simple backtracking alone; practical Wolfe searches may bracket and interpolate. Its existence theory assumes appropriate behavior along the search ray.

Repair the claim “The objective decreased at every iteration, so the algorithm found the global minimum.” Decreasing scalar values can converge while the iterates fail to settle, and nonconvex objectives can have nonglobal local minima. Separate finite descent evidence, stationarity convergence, iterate convergence and global optimality. Each requires its own assumptions or certificate.

Continue

Record direction slope, trial step, actual value, required bound and acceptance decision. This trace distinguishes a bad direction from an overly large step. Continue to Newton and quasi-Newton methods to use curvature in choosing directions. A full Newton step has powerful local guarantees under appropriate hypotheses, while damping and descent safeguards are needed to connect that local theory to more distant starting points.