A direction and a distance answer different questions. If , moving a little along lowers the objective. Moving almost no distance, however, may waste a useful direction. Moving too far may pass through a valley and climb its other side. The strong Wolfe conditions ask for both sufficient decrease and a suitably small directional slope. This section constructs a search that finds such a step under explicit assumptions; it also explains why multiplying the step by a constant smaller than one is not enough.
The construction uses only function and directional-derivative values along one ray. It does not require a convex objective, a Hessian, or an exact minimizer on the ray.
Reduce the search to one variable
Fix and a direction with . Define
Assume throughout the exact search that is continuously differentiable on and is bounded below there by a finite number . At zero the derivative is understood from the right. The usual continuously differentiable multivariable objective supplies this regularity on the ray. Choose fixed constants . Write
Definition 6.2.1
(Acceptable step)
A positive step is acceptable when
The first inequality is Armijo decrease. Because , acceptance improves the objective. The second bounds slopes on both sides of zero; a large positive slope fails even when the objective has decreased substantially. The labels “small step” and “large step” are therefore only informal descriptions. The actual tests concern values and slopes.
Concept lensAnalytic
Subtract the requested decrease
The residual turns Armijo into , while . Initially and . Thus is negative immediately to the right of zero. The positive tilt eventually forces upward when is bounded below. This residual explains both existence and the bracket argument; it is not a replacement objective for the outer optimization method.
An acceptable interval exists
Lemma 6.2.2
(Acceptable steps fill an open interval)
Under the standing assumptions on , and , the set of acceptable steps contains a nonempty open interval of positive numbers.
Proof
(Minimize the Armijo residual)
Since , choose with . The continuous function attains a minimum on . Its minimum is negative, because . Neither endpoint can attain that negative minimum, so some minimizing satisfies and . Consequently
Both acceptance inequalities are strict at . Continuity supplies an open interval around consisting entirely of acceptable positive steps.
This proves more than the existence of a single isolated solution, but it does not yet tell us which function evaluations will find that interval.
Worked example 6.2.3
(Acceptance without a line minimizer)
There need not be a line minimizer. For , the infimum zero is approached only as , and . Nevertheless, with and , the finite step satisfies and , so it is acceptable. An inexact line search solves an acceptance problem, not an exact minimization problem.
A bracket has an orientation
Definition 6.2.4
(Oriented bracket)
A bracket is a pair of distinct nonnegative endpoints . The endpoint is the retained acceptable-decrease point; bounds the region still being examined. They satisfy three invariants:
- and : the retained endpoint passes Armijo but has not passed strong curvature.
- : its derivative points downhill into the interval.
- Either or : the other endpoint fails Armijo or has not improved on the retained value.
Common mistake
(Sorting the endpoints)
The name “low endpoint” sometimes used for refers to its role and retained value, not its coordinate. It is quite possible that . Invariant 2 then requires , so traveling from toward decreases the objective initially. Sorting the endpoints and discarding their roles can break the algorithm.
At initialization is permitted: and . It is not itself a positive accepted step. Once zoom begins, the invariants describe information already obtained, rather than a claim that both endpoints satisfy Wolfe.
Expansion: obtain a bracket or a step
Choose an initial trial and expansion factor . Begin with and . Repeat the following policy in the displayed order.
- Evaluate . If or , call zoom with retained endpoint and other endpoint .
- Otherwise evaluate . If , return .
- If , call zoom with retained endpoint and other endpoint equal to the previous retained endpoint.
- Otherwise replace by , replace by , and continue.
In step 1 the retained endpoint has negative derivative of magnitude greater than : this holds at zero and after every previous expansion. The new other endpoint lies to its right, so all bracket invariants hold. In step 3, the new endpoint has passed Armijo and improved strictly on the previous retained value. It failed the curvature test, so its nonnegative derivative is actually greater than . The other endpoint is to its left and has larger function value. All invariants again hold, with the orientation reversed.
If no step or bracket were ever returned, the trials would be , and each would pass Armijo. Thus
which is impossible. Expansion therefore finishes after finitely many trials. In fact any trial larger than must fail Armijo. The algorithm need not know to use this proof. A fixed upper step cap changes the theorem, because the expanding trials may then never reach the required range.
Zoom: shrink the interval without losing its meaning
Starting with the three invariants, choose the midpoint and apply this policy:
- If or , set and repeat.
- Otherwise, if , return .
- Otherwise, if , first set to the old . Then set . If that product is negative, keep and set only . Repeat.
The derivative at is needed only after the value tests pass. In step 3, the product uses the endpoints from the beginning of that trial. Keeping an old copy of makes the assignment unambiguous. Every unsuccessful trial replaces the interval by one of its halves.
To verify preservation, first consider step 1. The old remains unchanged; the new lies in the same direction from it and satisfies invariant 3 by the rejection test. Next suppose the value tests pass but curvature fails. Then , and . If , the new retained point can keep the old . That endpoint still fails Armijo or has value at least the old retained value, hence strictly above the new one. If , replacing by the old reverses the interval orientation and leaves a strictly larger value at the other endpoint. The derivative is nonzero, so the product test has no ambiguous zero case after curvature has failed. This proves all three invariants after either update.
Theorem 6.2.5
(Finite strong Wolfe search in exact arithmetic)
Let be bounded below, with , and let . Geometric expansion with , , followed when needed by the midpoint zoom policy above, returns a positive step satisfying both strong Wolfe inequalities after finitely many trials. All comparisons and evaluations in this statement are exact.
Proof
(Nested intervals and a sign contradiction)
Expansion was proved finite. For zoom, suppose instead that infinitely many trials were rejected. The unordered closed intervals are nested, and their lengths tend to zero by halving. They have a common limiting point , and both labeled endpoints approach . Invariant 1 and continuity imply
Because , there is a neighborhood of on which and have the same fixed nonzero sign. To see this, if , continuity keeps nearby. If , continuity keeps nearby, so too.
Eventually the entire bracket lies in this neighborhood. Invariant 2 says that moving from to goes against that common derivative sign. Both functions strictly decrease along this move, giving
Neither alternative in invariant 3 can then hold. This contradiction proves finite zoom termination. Finally, a returned midpoint is positive: the interval is nondegenerate, both endpoints are nonnegative, and at least one is positive.
Proof X-ray
Why shrinking an interval is not the whole proof
Halving is spent on a single fact: the endpoints converge to one point . It does not by itself make , or any finite trial, acceptable; everything else comes from the invariants. Invariant 1 and continuity of keep , away from zero. The gap is needed on one side only: when it makes negative near , whereas when the positive term already gives . The key move is invariant 2, which orients the move from to against that common sign, so that would be better than in both senses at once. Invariant 3 forbids exactly this, and the contradiction excludes an infinite sequence of rejections. With the argument would stall at a limit with , where fixes no sign.
The same proof allows a safeguarded interpolation trial. Fix and require
Every unsuccessful update then leaves an interval of length at most . The invariant proof is unchanged and the nested intervals still shrink to one point. A cubic or quadratic interpolant can suggest , but its model accuracy is not used by this theorem; the interior safeguard supplies the required progress.
A quantitative bound when the derivative is Lipschitz
Continuous differentiability suffices for finite termination, but it does not provide a numerical modulus for how rapidly derivatives vary.
Proposition 6.2.6
(Minimum width of an unresolved bracket)
Suppose additionally that is -Lipschitz on the initial zoom interval, with . Every bracket inside it that satisfies the three invariants has width
Proof
(A narrow bracket cannot keep its orientation)
If the width were smaller and , every derivative inside would be less than . Hence both and would decrease from to the right-hand , contradicting invariant 3. If , every derivative would be greater than ; now , and both functions decrease when moving left from to . This gives the same contradiction.
After unsuccessful midpoint trials, the width would be . Therefore there cannot be consecutive unsuccessful trials whenever
This is a trial-count criterion, rather than an assumed stopping rule. For safeguarded interpolation replace by . A smaller safeguard or a smaller gap weakens this bound.
For an accepted step, Lipschitz continuity on the segment from zero to that step also gives
The second displayed bound concerns an accepted step and needs a derivative Lipschitz constant on that whole segment; a constant known only on a later zoom bracket need not suffice. If is -Lipschitz along the relevant multivariable segment, one may take . The numerical length depends on how is scaled; the displacement is what the objective sees.
Worked traces
Worked example 6.2.7
(The retained endpoint can lie on the right)
Let , and . Then . Armijo holds exactly for , while strong curvature holds exactly for . Their intersection is the latter interval.
Take the first trial . Its value is , but its derivative is . Expansion therefore enters zoom with , . At , the value improves on and passes Armijo, but the derivative fails curvature. Since , replace by the old , then set . The next midpoint is . Its value is and also , so both value tests pass. Its derivative is , within , and it is accepted. The accepted step is not the exact minimizer , and it need not be.
Worked example 6.2.8
(A nonconvex ray and value-based rejection)
Take , so , , and is negative near zero. The function is bounded below on the ray despite being nonconvex. Let , and initial trial . Since , zoom starts at .
The midpoint has value and derivative . Its value passes both tests, but curvature fails, giving . The next midpoint has value , which exceeds the retained value ; reject it without needing its derivative and set . At the value still exceeds , so set . At the value is , Armijo holds, and the derivative is , whose magnitude is below . Accept . Convexity was never used in the invariant or termination proof.
What can fail, and what a computer can certify
Counterexample mode
Backtracking can miss every acceptable step
For , choose , . Strong curvature requires . Starting at and repeatedly halving produces only steps below . All these small steps pass Armijo, but none passes strong curvature. A loop that halves whenever either strong Wolfe condition fails therefore runs forever in exact arithmetic. Expansion is needed when the slope remains too negative; shrinking is not the universal response to failure.
The hypotheses also have concrete roles. Without the ray lower bound, passes Armijo at every positive step, but everywhere. Without descent, at zero has no acceptable positive step: the Armijo right side is zero and . With an artificial cap, even a smooth strongly convex ray can defeat the search: for , , , strong curvature requires . A cap excludes every acceptable step.
Exact comparison is another substantive assumption. In floating-point arithmetic, a midpoint can round to an endpoint once the endpoints are adjacent representable numbers. Then the interval does not shrink, and the exact theorem no longer applies to that loop.
Common mistake
(Reporting a tiny bracket as success)
A bounded evaluation budget, an invalid objective value, a failed derivative computation or such stagnation should produce an explicit search-failure status unless acceptance has actually been verified. An interval-width tolerance alone is not a strong Wolfe certificate. Similarly, an arbitrarily small parameter step can correspond to a numerically unchanged point .
If rigorous evaluation error bounds are available, the acceptance tests can incorporate them. Suppose computed values have absolute errors at most , respectively. A sufficient certificate for true Armijo is
A sufficient certificate for true strong curvature is
together with to certify descent. These formulas follow from the triangle inequality; they can be conservative. They do not prove termination of a complete finite-precision implementation, and an empirically estimated error is not automatically a rigorous bound.
Why the outer method needs this search
Let and . Any accepted step has
This supplies the positive curvature pair needed by the positive-definite BFGS update proved earlier. Weak Wolfe would already suffice for this particular inequality; strong Wolfe additionally limits the positive slope after a possible overshoot. A search that fails and returns an arbitrary fallback step cannot invoke this curvature proof without checking that step separately.
Under the Lipschitz-gradient and lower-bound hypotheses of the Wolfe angle theorem, strong Wolfe supplies the weak Wolfe condition that theorem uses, and hence the same weighted gradient series. To conclude that gradient norms tend to zero, one still needs a uniform positive direction-angle bound or other appropriate outer-method analysis. Finite success of each line search does not prove that a whole BFGS or nonlinear conjugate-gradient sequence converges, nor that a nonconvex stationary point is a global minimizer.
Exercises
Quick check
(For , derive the complete positive acceptance interval for arbitrary . State when the upper endpoint comes from Armijo rather than curvature.)
Solution
Armijo becomes , so . Strong curvature becomes , or . The intersection is . It is nonempty because follows from . Armijo supplies the smaller upper endpoint when ; equality makes both constraints active at the same endpoint.
Quick check
(For , , , start expansion at with . Trace the trials until acceptance.)
Solution
The initial slope is . At and , the values are approximately and , below their Armijo bounds and and improving on the retained values. Their slope magnitudes exceed , so expand. At , the value and slope magnitude are both approximately ; Armijo and strong curvature pass. The procedure accepts without ever bracketing a finite exact minimizer.
Quick check
(A zoom bracket has width , , , and derivative Lipschitz constant . Give a number of consecutive unsuccessful midpoint trials that the quantitative proof rules out. Does that number certify any particular trial before evaluation?)
Solution
The forbidden width threshold is . Five unsuccessful trials would leave width , impossible for a preserved bracket. Thus acceptance occurs within the first five midpoint evaluations. Four failures are not excluded by this bound, since . The proof bounds a valid exact search; it does not mark a trial acceptable without checking its value and derivative.
Quick check
(Suppose a quadratic interpolation proposal always lies strictly inside the bracket, but the successive width factors are for . Explain why strict interior placement alone does not prove that the widths tend to zero. Contrast a fixed safeguard.)
Solution
Set . For finitely many factors in , induction gives . Here the full sum is , so every finite product is at least , and the decreasing products have a positive limit. These hypothetical width factors therefore leave at least half the original width. A fixed instead gives . This calculation exposes a missing implication in an unsafeguarded proof; it does not claim that every interpolating search actually follows those factors.
Quick check
(A computed Armijo residual is . Suppose and . Does the error-aware test certify Armijo? If , , and both derivative errors are , does it certify descent and strong curvature?)
Solution
The total Armijo residual-error bound is , leaving the certified upper residual , so Armijo is certified. Descent is certified by . For curvature the sufficient left side is , while the right side is ; the test does not certify it. Failure of this sufficient certificate alone does not prove that the true strong curvature inequality is false.