Why a local model needs a global safeguard
Newton's method minimizes a quadratic model at the current point. For a twice continuously differentiable objective , write and . If is positive definite, the model
has the unique minimizer . Near a nondegenerate minimizer this direction is remarkably effective. Far away, however, a model that is accurate for small need not predict what happens at the full step . A line search keeps the direction but tests its length against the actual function.
We distinguish two goals. Global convergence below means convergence of the gradient to zero from an arbitrary starting point under stated assumptions; it does not mean convergence to a global minimizer. Local quadratic convergence is a stronger rate near a suitable minimizer. The first result makes no promise that a particular stationary point is reached.
Descent and the Armijo test
Definition 1.8.1
(Backtracking line search)
Choose and . Given and a direction satisfying , start with . Until
replace by . Accept the first tested length satisfying (1), and set . This is the Armijo sufficient-decrease condition.
The right side is strictly below , so an accepted step lowers the objective. It asks for a fraction of the decrease predicted by the linear term, not the full model decrease. If and is symmetric positive definite, is a descent direction because . At one should stop; the strict descent condition does not apply.
Theorem 1.8.2
(Termination of backtracking)
Suppose has an -Lipschitz gradient on , with , and . Then the backtracking procedure terminates. In fact every with
satisfies (1).
Proof
(A quadratic upper bound along the ray)
By integrating the gradient along the segment and applying the Lipschitz inequality,
The last two terms are at most precisely when the stated sufficient bound holds. Since , a tested length eventually falls below that positive bound. This is a sufficient threshold, not necessarily the largest acceptable length.
A global stationarity guarantee
Theorem 1.8.3
(Gradient convergence for uniformly positive Newton matrices)
Let have an -Lipschitz gradient, and let be bounded below on the initial level set . Suppose that on the Hessian satisfies
for constants . At each nonstationary iterate use the Newton direction and Armijo backtracking with fixed . Then either an iterate is stationary or .
The Hessian bounds are strong assumptions, and they are not implied by the existence of a minimizer. They give a uniformly controlled direction on the level set. The proof also explains why merely knowing that each individual step decreases would not suffice: decreases could be so tiny that their sum remains finite while the gradient stays large.
Proof
(Uniform decrease and a summable series)
Accepted steps decrease , so all iterates stay in . The eigenvalue bounds imply
Thus the sufficient threshold from the previous theorem is at least . If , the first tested step is accepted; otherwise the first accepted step is larger than unless it was already 1. In either case all accepted steps satisfy . Armijo now gives
Summing from to telescopes. The left side is bounded above by , so and its nonnegative terms tend to zero.
Proof X-ray
Which hypothesis buys which inequality
The argument converts per-step decrease into a uniform one, and every hypothesis is spent on one link. The upper bound makes the Newton direction steep enough, ; the lower bound keeps it short, . Together with the Lipschitz constant they put a floor under the acceptable step that does not depend on , and backtracking by the fixed factor can overshoot that floor by at most one factor, which gives . Armijo then turns the floor into a decrease proportional to . Monotone decrease is used once more, to keep every iterate in where the Hessian bounds hold. The closing move is the telescoping sum: boundedness below makes the total decrease finite, so is summable. Remove and the floor can collapse; remove boundedness below and the sum need not be finite.
The exact linear solve matters to this proof: a computed direction must still satisfy suitable descent and size inequalities. Inexact solves, indefinite Hessians and trust-region methods require their own safeguards; replacing by an arbitrary matrix does not inherit this theorem automatically.
When full Newton steps return
Theorem 1.8.4
(Full steps and quadratic convergence near a strict minimizer)
Suppose is stationary, is positive definite, the Hessian is Lipschitz in a neighborhood of , and . Then for every sufficiently close to , backtracking accepts at every step and the iterates converge quadratically to .
Proof
(The cubic remainder is eventually dominated)
For sufficiently close to , the Hessian remains uniformly positive definite. With , the second-order expansion gives
Since is bounded below by a positive multiple of , the cubic remainder is eventually dominated by . Hence the full step satisfies (1). The restriction leaves room for the remainder; it is sufficient, not claimed necessary for every function.
For the rate, write . The integral form of the gradient and yield
The locally bounded inverse and Lipschitz Hessian give . Thus a sufficiently close start stays in the neighborhood, takes full steps and converges quadratically. This is a local theorem; the global stationarity result by itself does not assert that its iterates enter that neighborhood.
Proof X-ray
Why the full step survives and then squares the error
The proof has two independent halves. Acceptance: because , the quadratic term cancels half the linear one, , so the true decrease is half the predicted linear decrease up to the cubic remainder that the Lipschitz Hessian controls. Positive definiteness near makes comparable to , and supplies the slack that absorbs that remainder once is small. Rate: the error identity writes as times Hessian differences of size acting on . The argument closes by induction: once the next iterate is closer, so both halves apply again. None of the global hypotheses is used.
Common mistake
(Choosing and expecting full steps)
The restriction is not cosmetic. For the full Newton step lands exactly on the minimizer, and while . Armijo with demands , which is false, so the exact step is rejected. Then is accepted, because , and the iteration becomes : linear convergence on a quadratic.
A step that must be shortened
Worked example 1.8.5
(Exponential objective)
Take , , , and . Here , , and the unique minimizer is . The Newton direction is
The full step gives and increases enormously. At , , and ; this is below , but it exceeds the Armijo right side , so simple decrease is not enough. At , , , while the right side is approximately ; this length is accepted. The gradient is not globally Lipschitz on , so the preceding global theorem cannot be invoked as stated for this example.
Common mistake
(Accepting any decrease)
At in the example above, did decrease, from about to . Accepting such steps gives no lower bound on the decrease in terms of , which is exactly what the stationarity proof needs; Armijo rejects it because it achieves less than a quarter of the predicted linear decrease.
Worked example 1.8.6
(Full steps take over near the minimizer)
Continue from the accepted point with full steps. Here the Newton update is . At the full step gives , below the Armijo right side , so is accepted, as are all later full steps. The iterates are approximately
The ratios are about , , and : the error is squared at each step, with a constant tending to . The global phase needed one shortened step; after that the local theorem describes the behavior.
Worked example 1.8.7
(The uniform step floor for a strongly convex objective)
Let . Then on all of , so , , and is -Lipschitz; is bounded below by . With and the proof gives and , hence a guaranteed decrease of at least . From : , , . The full step gives and , below the Armijo right side , so is accepted. The actual decrease is far above the guaranteed : the theorem's constants certify convergence, not speed.
Counterexample mode
Positive curvature is not optional in the descent argument
For at , we have and . The Newton equation gives , so : the direction is ascent. For sufficiently small positive , , whereas the Armijo right side is also above . The descent-based termination proof therefore does not apply. With the backtracking loop in fact never stops: , and for every because its minimum, at , is about . A method must detect or modify such a direction.
Practice with solutions
Quick check
(Let , and . Find the Newton direction and test .)
Compare with .
Solution · Answer
, , so . The new value is , while the Armijo right side is ; the full step is accepted.
Quick check
(If has eigenvalues in with , show .)
Use .
Solution · Answer
Diagonalize the symmetric ; the eigenvalues of lie in . Thus .
Quick check
(Why does decreasing and bounded below not alone imply ?)
Consider what convergent values say about each decrease.
Solution · Answer
Convergence of the objective values only implies successive decreases tend to zero. Without a lower bound tying each decrease to , that says nothing about gradients. For instance, , has decreasing values bounded below and gradient always 1; it illustrates the logical gap, not a Newton sequence satisfying the theorem.
Quick check
(Let , starting at . What does full Newton iteration do?)
Compute .
Solution · Answer
, so and , but has no finite limit and has no stationary point. Its Hessian has no uniform positive lower bound along the iterates. Gradient convergence is not automatically convergence of the iterates.