Motivation
Choosing a descent direction only says that a sufficiently short move will improve the objective. It does not tell us how far to move, whether a practical search finds such a step, or what repeated moves accomplish. Line searches make that local information operational: Armijo tests actual decrease, while Wolfe adds a slope condition preventing a step from remaining arbitrarily short. These tests are not themselves global optimization certificates. Their convergence results require assumptions on smoothness, the objective's lower bound, and the directions.
Newton's method uses curvature to choose a direction, and can converge much faster near a nondegenerate minimizer. Far from such a point its Hessian may be singular or indefinite, so its step need not be a descent direction. We first establish guarantees for a general search and then prove the local Newton rate under separate, stronger hypotheses.
Definitions
Let be continuously differentiable. At write , choose with , and set .
Definition 6.1.1
(Armijo, weak Wolfe and strong Wolfe conditions)
Let and let be a descent direction. A positive step satisfies the weak Wolfe conditions when
The first inequality alone is the Armijo sufficient-decrease condition; the second is a curvature condition. The strong Wolfe conditions keep Armijo and replace the second inequality by . Armijo backtracking starts from and repeatedly multiplies the trial step by until Armijo holds.
Strong Wolfe implies weak Wolfe but is more restrictive. Backtracking does not promise the Wolfe curvature condition; it prevents tiny steps by a different mechanism, examined in the first proof below.
Definition 6.1.2
(Angle factor)
For and a descent direction , the angle factor is .
It measures alignment with negative gradient. Scaling changes the numerical step length but not this angle. When , the factor equals one.
Theorem/Proposition
Theorem 6.1.3
(Armijo backtracking gives a gradient convergence bound)
Suppose has an -Lipschitz gradient and is bounded below by . Use and Armijo backtracking with fixed , and . Then every search at a nonstationary iterate terminates, the accepted steps have a common positive lower bound, and
Thus the gradient norms tend to zero unless the method stops at a stationary point.
The Wolfe conditions are useful only if acceptable steps exist; the next lemma settles this along any descent direction.
Lemma 6.1.4
(Existence of weak Wolfe steps)
Let be continuously differentiable, let be a descent direction at , and suppose is bounded below on . For every there is a step satisfying the weak Wolfe conditions.
With such steps available, the decrease they force can be summed.
Theorem 6.1.5
(Wolfe angle theorem)
Suppose is bounded below and has an -Lipschitz gradient. If every is a descent direction and every step satisfies weak Wolfe, then
If in addition uniformly, then .
Near a nondegenerate minimizer, curvature gives a much stronger local statement.
Theorem 6.1.6
(Local quadratic convergence of Newton's method)
Let be twice continuously differentiable near with and positive definite, and let the Hessian be -Lipschitz on a convex neighborhood of . Then there are and such that, for every with , the full Newton iterates are defined, converge to , and satisfy
For gradient descent, strong convexity upgrades the Armijo result from stationarity to a rate for the objective.
Proposition 6.1.7
(Linear rate under strong convexity)
Under the hypotheses of the Armijo backtracking theorem, suppose in addition that is -strongly convex with minimizer . Then
the factor lies in , and .
A stationary point can be a maximum or saddle. The theorems do not claim that the iterates converge or that the objective reaches its global minimum. The angle hypothesis is essential to the stated gradient conclusion: descent directions can become almost perpendicular to the gradient.
Proof sketch or proof idea
Backtracking and its uniform step bound
Proof
(Descent lemma and a uniform step bound)
The descent lemma gives . Therefore Armijo holds whenever . Backtracking must reach that interval. If the initial step is not accepted, the accepted step is greater than times the threshold; if the initial step is accepted, it equals . Hence every accepted step is at least
The Armijo decrease then bounds by , which is at most . Dividing by proves the displayed minimum bound. The same finite sum of squared gradients proves the individual gradient norms tend to zero. This is a stationarity guarantee with an explicit complexity bound, not an assertion that all iterates are close to a unique point.
Existence and consequences of Wolfe steps
Proof
(Rolle's theorem on the Armijo gap)
For a fixed descent direction, put and . Initially and , so for small positive steps. If is bounded below along the ray, eventually becomes positive because grows without bound. Before its first positive zero, Armijo holds; Rolle's theorem on the interval from zero to that first root gives an interior point where . There , since . Thus a weak Wolfe step exists. This is an existence proof, not a guarantee that simple Armijo backtracking will find it.
Proof
(A lower bound on each step, then summation)
For an accepted step, weak Wolfe and Lipschitz continuity give
Combining this lower bound on with Armijo yields
Summing from to bounds the partial sums of by , which proves the Wolfe angle theorem. If , then , so . Without that angle bound, only the weighted series is controlled.
Proof X-ray
Each Wolfe condition does one job
The argument converts a step length into a decrease, and each Wolfe inequality supplies one half. The curvature condition is spent first: together with the Lipschitz gradient it says the slope cannot change by unless the step is at least , so accepted steps cannot be arbitrarily short. Armijo is spent second: it turns any accepted step into a decrease of at least . The key move is multiplying the two bounds, which produces ; this quantity does not change when is rescaled, which is why the conclusion is stated through the angle and not through step lengths. The lower bound on closes the argument by making the telescoping sum of decreases finite. If were allowed to equal one, the factor would vanish and the step bound would be empty; if were unbounded below, the sum could diverge, as the counterexample later in this section shows.
Newton's local quadratic rate
Proof
(Integrate the Hessian along the error)
Work under the hypotheses of the Newton theorem. Continuity gives a ball around on which is invertible and ; the curvature argument at the end of this section gives the explicit choice . For the full Newton step , write , so that . Since , and ,
Choose no larger than the radius of that ball and with . Then gives , so the next iterate stays in the ball. Induction gives convergence and the quadratic estimate at every step.
Proof X-ray
Where the square comes from
Everything rests on rewriting the new error, using , as : the inverse Hessian applied to the defect of a linearization. The integral form of turns that defect into an average of Hessian differences, and the Lipschitz bound integrates to ; one factor comes from the defect and one from the vector it acts on. Positive definiteness of enters only through continuity, to give invertibility and on a ball. The choice makes the error contract, which keeps each iterate in the ball and lets the induction close.
Positive definiteness of also makes a strict local minimum. The result concerns full Newton steps sufficiently near ; it is not a global theorem for arbitrary starting points, singular Hessians, or arbitrary damped steps.
Concept lensAlgorithmic
Two descriptions of one Newton step
The step is the stationary point of the quadratic model , since . It is also the Newton root-finding step for the equation , which linearizes . The local proof above uses only the second description: it never compares function values, so it holds equally near a saddle or maximizer where is merely invertible. The model description adds what root-finding lacks: when is positive definite, minimizes and, when , is a descent direction.
Eventual acceptance of full Newton steps
Under the same local assumptions, remains uniformly positive definite. For , Taylor expansion gives . Since and the positive quadratic term dominates the cubic remainder, Armijo with accepts sufficiently near . This justifies recovering full Newton's quadratic rate after a suitable damped method has entered that neighborhood; entering it is an additional issue, not proved by the local argument.
A rate under strong convexity
The preceding Armijo theorem proves stationarity without assuming convexity. Strong convexity gives a stronger, objective-value conclusion.
Proof
(Gradient domination plus Armijo)
Under the hypotheses of the strong-convexity proposition, the strong convexity inequality at , evaluated at , gives
The second inequality minimizes the quadratic expression over all displacements. Thus . Armijo and the uniform lower bound on the step imply , and subtracting gives the displayed inequality of the proposition. The coefficient is nonnegative under these assumptions: for a differentiable -smooth strongly convex function, and . Hence the objective gap decreases at least geometrically by iterating the inequality. Strong convexity also gives , so the iterates converge to the unique minimizer.
This rate depends on actual constants and the prescribed search parameters; it does not claim that the bound is sharp.
A descent direction can still make little progress
Consider and directions that are almost perpendicular to the gradient. At any nonzero , take a unit vector perpendicular to and choose . Then when , but the cosine can approach zero as . A direction can therefore satisfy the literal descent test while conveying very little decrease in the gradient direction. The angle theorem correctly records the weaker weighted conclusion unless a uniform angle bound is proved.
The lower-bound assumption also has a concrete role.
Counterexample mode
Without a lower bound the gradient need not vanish
Drop only the lower bound from the Armijo backtracking theorem. The function on has gradient everywhere, which is -Lipschitz for every . With , the Armijo test holds for every because , so backtracking accepts at once and . Each step decreases by , yet for every , and there is no stationary point at all. The total decrease is unbounded, so the summation step of the proof has nothing finite to divide by . With restored, the total decrease is at most and the theorem holds.
In contrast, if a bounded-below objective has an accumulation point and continuous gradient, gradient convergence implies that every such accumulation point is stationary. Existence of an accumulation point itself requires a compactness or boundedness argument and is not automatic.
Why local Newton curvature controls the step
The local inverse bound used in the Newton proof follows directly from positive definiteness. Let the smallest eigenvalue of be . By continuity, sufficiently near we have . Thus for any vector ,
Consequently is invertible and . The same estimate proves for a nonzero Newton step in this neighborhood. Away from it, continuity at gives no such bound. An algorithm that replaces an indefinite Hessian with an SPD approximation may restore descent, but the modification and its influence on the local rate must be analyzed separately.
For the unit-step Armijo statement, Lipschitz continuity of the Hessian bounds the Taylor remainder in absolute value by . If , then . When , the positive margin dominates the cubic remainder for small . Explicitly comparing these two terms proves the test; merely saying that Newton is locally accurate would not identify the required restriction on .
The search parameters also express a tradeoff. A smaller backtracking factor can overshoot far below the threshold that would have been accepted, weakening the lower bound , even though termination still holds. A small asks for less decrease per step, while a value near one makes sufficient decrease more demanding. The convergence proof works for every fixed value in the stated interval; it does not identify a universally best choice for computational cost.
A stopping test based on must also respect scaling. Replacing by a positive constant multiple leaves its minimizers unchanged but scales its gradient, so the same numerical tolerance has a different meaning. When strong convexity with known applies, the inequality converts a gradient tolerance into an objective-gap certificate. Without such structure, a small gradient alone supplies only an approximate stationarity statement.
To verify , strong convexity gives . Cauchy–Schwarz and Lipschitz continuity bound the same product above by . For distinct points, division proves the inequality. Both assumptions are used; neither constant is an algorithmic step size. If these bounds are known only on a local region, the corresponding derivation applies only while the iterates actually remain in that region; the global theorem cannot be applied directly.
Worked examples
Worked example 6.1.8
(An Armijo search by hand)
For at , take , , initial step one and . At the new value is one, but the Armijo right side is , so reject. At both sides are zero, so accept and reach the minimum. The inequality allows equality.
Worked example 6.1.9
(Wolfe slopes on a quadratic)
For the same , let and . At , the new point is zero and the new directional derivative is zero. Armijo holds and , so weak Wolfe holds. The curvature test prevents arbitrarily tiny steps: here it requires .
Worked example 6.1.10
(Newton on a scalar quadratic)
For with , the gradient is and Hessian . The Newton step is , so a full step reaches in one iteration. The Hessian Lipschitz constant is zero, making the quadratic error bound exact with zero right side. This special behavior does not mean general nonlinear objectives solve in one step.
Common mistakes
Common mistake
(Treating Armijo as a Wolfe test)
Armijo alone controls decrease, not curvature. For at with and , the tiny step passes Armijo, since , but fails the curvature condition with , which needs . Likewise a weak Wolfe step need not satisfy strong Wolfe, which also bounds a positive new slope.
Common mistake
(Expecting every positive step to decrease)
A descent direction only promises decrease for sufficiently small steps. For at with , the step lands at with no decrease, and every increases . Conversely, a small gradient at the end is not a global-optimality proof for a nonconvex objective: it may sit near a maximum or a saddle.
Common mistake
(Using the Newton step away from the local theory)
Newton's inverse-Hessian formula presumes invertibility, and an indefinite Hessian can turn the Newton direction into ascent, as the exercise below on shows. Local quadratic convergence does not assert that a distant initial point reaches the local neighborhood.
Summary
Backtracking turns the descent lemma into a uniform step bound for gradient descent. Wolfe's slope condition produces a decrease estimate weighted by the direction angle. Newton's method gains a quadratic local rate from a nonsingular positive definite Hessian and Lipschitz Hessian variation; damped steps and global convergence need additional analysis.
Exercises
Quick check
(For at and , find the Armijo range for .)
Write both sides of the Armijo inequality as functions of .
Solution · Answer
Armijo requires , equivalent to . Thus positive steps satisfy .
Quick check
(Under the Wolfe angle theorem with , explain why .)
Compare the weighted series with .
Solution · Answer
The theorem gives . The angle bound implies , so each nonnegative term tends to zero.
Quick check
(Find the Newton direction for at and show that it is not a descent direction.)
Compute the sign of .
Solution · Answer
Here and , so . The directional product is , hence the direction is ascent. The step reaches the stationary maximum at zero.
Quick check
(For , find the full Newton update and show that its error is at most .)
The minimizer is .
Solution · Answer
The gradient is and Hessian , giving . The minimum is at zero and , a stronger local estimate than a generic quadratic bound.