44.03.01 · optimization-control / unconstrained-optimization

Line-Search Methods: Wolfe Conditions and Global Convergence

shipped3 tiersLean: none

Anchor (Master): Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §3.2-3.3 (Zoutendijk's theorem, the angle condition, global convergence of line-search methods to stationary points, and the linear convergence rate of steepest descent with the condition-number-dependent constant); Zoutendijk 1970 Nonlinear programming, computational methods (in Abadie, ed., North-Holland); Bertsekas 2016 Nonlinear Programming 3e (Athena Scientific) §1.2

Intuition Beginner

Most methods for minimising a function of many variables work the same way: from where you stand, pick a direction that heads downhill, then decide how far to walk along it before stopping to look around again. The direction is the easy part — the gradient tells you the steepest uphill way, so its opposite points downhill. The hard part is the second decision: how big a step to take.

Take too small a step and you barely move, so the method crawls and may need thousands of stops to get anywhere. Take too big a step and you can overshoot the bottom of the valley and end up higher than where you started, which is worse than not moving at all. The whole art of a line search is choosing a step length that makes real, lasting progress without overshooting.

You do not need the perfect step — finding the exact lowest point along the line is itself a hard one-dimensional problem you would rather not solve every iteration. You only need a step that is "good enough". Two plain requirements capture good enough. First, the function value should drop by a fair amount, not a token amount: this rules out steps that are too short relative to how steeply you set off. Second, the slope should flatten out: by the end of the step the ground should be much less steep downhill than it was at the start, which rules out stopping while you are still plunging steeply and could gain more.

These two requirements together are the Wolfe conditions, and almost every serious optimisation method leans on them.

Visual Beginner

Imagine slicing the landscape with a vertical knife along your chosen downhill direction. What you see on the cut face is a one-dimensional curve: height versus how far you have walked, written $ϕ (α) = f (x + α p)$ , where $α$ is the distance and $p$ is the direction. You start at $α = 0$ heading downhill, so the curve slopes down to the right at first.

The first rule draws a straight reference line starting at $ϕ (0)$ but tilted only a fraction as steeply as the true initial slope. Any step whose height lands on or below that gentle line counts as "enough decrease". The second rule looks at the slope of the curve where you stop: it must be noticeably less steep (less negative) than the slope you started with.

step length	enough decrease?	slope flattened?	verdict
far too small	yes, but tiny	no, still plunging	rejected (too short)
far too large	no, overshot upward	—	rejected (too long)
near the dip	yes	yes	accepted (Wolfe)

The takeaway: the two rules carve out an interval of acceptable step lengths sitting around the bottom of the sliced curve. You do not have to hit the exact bottom; you only have to land inside that interval, and a short search always can.

Worked example Beginner

Let us minimise $f (x_{1}, x_{2}) = x_{1}^{2} + 4 x_{2}^{2}$ , a stretched bowl with its bottom at the origin. Start at the point $x = (1, 1)$ . The downhill direction we use is the negative gradient. The gradient (the pair of slopes in the two coordinate directions) is $(2 x_{1}, 8 x_{2})$ , so at our point it is $(2, 8)$ and the search direction is its opposite, $p = - (2, 8) = (- 2, - 8)$ .

Walking a distance $α$ gives the point $x + α p = (1 - 2 α, 1 - 8 α)$ , and the sliced curve is

ϕ (α) = (1 - 2 α)^{2} + 4 (1 - 8 α)^{2} .

Its starting height is $ϕ (0) = 1 + 4 = 5$ , and its starting slope is $- (2^{2} + 8^{2}) = - 68$ (the negative of the gradient's squared length, because we walk straight down the gradient).

The first Wolfe rule, with the usual mild fraction $c_{1} = 0.1$ , accepts a step if $ϕ (α) \leq 5 - 0.1 \cdot 68 \cdot α = 5 - 6.8 α$ .

Try $α = 0.05$ : the point is $(0.9, 0.6)$ , and $ϕ = 0.81 + 4 (0.36) = 0.81 + 1.44 = 2.25$ . The threshold is $5 - 6.8 (0.05) = 5 - 0.34 = 4.66$ . Since $2.25 \leq 4.66$ , the decrease rule passes comfortably.

Now check the slope at the stop. Differentiating, $ϕ^{'} (α) = 2 (1 - 2 α) (- 2) + 8 (1 - 8 α) (- 8)$ . At $α = 0.05$ : $ϕ^{'} (0.05) = - 4 (0.9) - 64 (0.6) = - 3.6 - 38.4 = - 42$ . With curvature fraction $c_{2} = 0.9$ , the slope must satisfy $ϕ^{'} (α) \geq 0.9 \cdot (- 68) = - 61.2$ . Since $- 42 \geq - 61.2$ , the curvature rule also passes.

What this tells us: a single step of length $0.05$ cut the height from $5$ to $2.25$ and flattened the slope from $- 68$ to $- 42$ , and it satisfies both Wolfe conditions. We made solid progress without solving the exact one-dimensional minimisation.

Check your understanding Beginner

Exercise (easy, multiple-choice).

Why do we use the sufficient-decrease (Armijo) rule rather than just asking that the function value drop at all?

Because any drop, however tiny, is impossible to achieve.
Because a sequence of tinier and tinier drops can stall short of the minimum, so we demand the drop be a fair fraction of what the slope predicts.
Because the function might increase.
Because the gradient is unavailable.

Hint

Picture steps that each shave off a vanishing sliver of height; do they ever reach the bottom?

Answer

B. Merely insisting on some decrease lets the steps shrink so fast that the running total of progress is finite and the method halts above the minimum. The Armijo rule ties the required drop to the initial slope and the step length, so each accepted step earns its keep. Feedback-correct: tying decrease to the slope blocks the stall. Feedback-wrong: A and C misread the setup; D is irrelevant since the rule uses the slope precisely when it is available.

Formal definition Intermediate+

Let $f : R^{n} \to R$ be continuously differentiable with gradient $g (x) = \nabla f (x)$ . A line-search method generates iterates by

x_{k + 1} = x_{k} + α_{k} p_{k}, α_{k} > 0,

where $p_{k} \in R^{n}$ is a search direction and $α_{k}$ is the step length. The direction $p_{k}$ is a descent direction at $x_{k}$ if

g_{k}^{⊤} p_{k} < 0, g_{k} := \nabla f (x_{k}),

so that $f$ decreases along $p_{k}$ for small $α$ . The angle $θ_{k}$ between $p_{k}$ and the steepest-descent direction $- g_{k}$ is given by

cos θ_{k} = \frac{- g _{k}^{⊤} p _{k}}{∥ g _{k} ∥ ∥ p _{k} ∥} \in (0, 1] .

The restriction of $f$ to the ray is the one-dimensional merit function

ϕ_{k} (α) = f (x_{k} + α p_{k}), ϕ_{k} (0) = f (x_{k}), ϕ_{k}^{'} (0) = g_{k}^{⊤} p_{k} < 0.

Fix constants $0 < c_{1} < c_{2} < 1$ . The Armijo (sufficient-decrease) condition requires

f (x_{k} + α p_{k}) \leq f (x_{k}) + c_{1} α g_{k}^{⊤} p_{k}, i.e. ϕ_{k} (α) \leq ϕ_{k} (0) + c_{1} α ϕ_{k}^{'} (0) .

The curvature condition requires

\nabla f (x_{k} + α p_{k})^{⊤} p_{k} \geq c_{2} g_{k}^{⊤} p_{k}, i.e. ϕ_{k}^{'} (α) \geq c_{2} ϕ_{k}^{'} (0) .

Together these are the (weak) Wolfe conditions. The strong Wolfe conditions replace the curvature condition by the two-sided bound

\nabla f (x_{k} + α p_{k})^{⊤} p_{k} \leq c_{2} g_{k}^{⊤} p_{k},

which additionally rules out points where the slope has turned strongly positive (overshoot past a local minimiser of $ϕ_{k}$ ). The Goldstein conditions bracket the decrease from both sides with a single constant $c \in (0, \frac{1}{2})$ :

f (x_{k}) + (1 - c) α g_{k}^{⊤} p_{k} \leq f (x_{k} + α p_{k}) \leq f (x_{k}) + c α g_{k}^{⊤} p_{k},

the right inequality being sufficient decrease and the left preventing too-short steps without using a gradient evaluation at the trial point.

The backtracking line search uses only the Armijo condition: starting from an initial $\overset{α}{ˉ} > 0$ and a contraction $ρ \in (0, 1)$ , it repeatedly sets $α \leftarrow ρ α$ until the Armijo inequality holds. The new symbols $g_{k}$ (gradient), $ϕ_{k}$ (one-dimensional merit function), $θ_{k}$ (search-angle), and the constants $c_{1}, c_{2}$ are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"Sufficient decrease alone guarantees progress to the minimum." Armijo by itself admits arbitrarily short steps: for any descent direction the inequality holds for all small enough $α$ , so a method that always picks a minuscule $α$ satisfies it while stalling. The curvature (or Goldstein lower) condition is what excludes too-short steps.
"The Wolfe conditions force $α_{k}$ near the exact one-dimensional minimiser." They only carve out an interval. A step can satisfy the weak Wolfe conditions while the slope there is positive (past the dip); the strong Wolfe conditions are needed to keep $α_{k}$ close to a stationary point of $ϕ_{k}$ .
*"Any direction with $g_{k}^{⊤} p_{k} < 0$ gives global convergence."* Descent is necessary but not sufficient. If the directions become nearly orthogonal to $- g_{k}$ (so $cos θ_{k} \to 0$ ), Zoutendijk's sum can converge with $∥ g_{k} ∥ \neq \to 0$ ; the angle condition $cos θ_{k} \geq δ > 0$ is the extra hypothesis that rescues convergence.
"Steepest descent converges quadratically like Newton." On a strongly convex quadratic, steepest descent with exact line search converges only linearly, with factor $((κ - 1) / (κ + 1))^{2}$ in the energy norm; an ill-conditioned Hessian ( $κ$ large) makes this factor close to $1$ and the method crawls. The condition number, not the dimension, governs the rate.

Key theorem with proof Intermediate+

The signature result of line-search theory is Zoutendijk's theorem: under the Wolfe conditions and a Lipschitz gradient, the gain of each step, measured as $cos^{2} θ_{k} ∥ g_{k} ∥^{2}$ , is summable. Summability is the engine that converts a local acceptance rule into a global convergence statement, and it is the single inequality from which convergence to stationary points follows for every angle-bounded method.

Theorem (Zoutendijk). Let $f : R^{n} \to R$ be continuously differentiable and bounded below on the level set ${x : f (x) \leq f (x_{0})}$ , with gradient $\nabla f$ Lipschitz continuous of constant $L$ on an open set containing that level set. Consider any line-search method $x_{k + 1} = x_{k} + α_{k} p_{k}$ in which each $p_{k}$ is a descent direction and each $α_{k}$ satisfies the Wolfe conditions with fixed $0 < c_{1} < c_{2} < 1$ . Then

k = 0 \sum \infty cos^{2} θ_{k} ∥ g_{k} ∥^{2} < \infty.

Proof. From the curvature condition at the accepted step, $g_{k + 1}^{⊤} p_{k} \geq c_{2} g_{k}^{⊤} p_{k}$ , so subtracting $g_{k}^{⊤} p_{k}$ from both sides gives

(g_{k + 1} - g_{k})^{⊤} p_{k} \geq (c_{2} - 1) g_{k}^{⊤} p_{k} .

The right side is positive because $c_{2} < 1$ and $g_{k}^{⊤} p_{k} < 0$ . On the other side, the Lipschitz bound gives $∥ g_{k + 1} - g_{k} ∥ \leq L ∥ x_{k + 1} - x_{k} ∥ = L α_{k} ∥ p_{k} ∥$ , so by Cauchy-Schwarz $(g_{k + 1} - g_{k})^{⊤} p_{k} \leq L α_{k} ∥ p_{k} ∥^{2}$ . Combining the two inequalities,

(c_{2} - 1) g_{k}^{⊤} p_{k} \leq L α_{k} ∥ p_{k} ∥^{2} ⟹ α_{k} \geq \frac{c _{2} - 1}{L} \frac{g _{k}^{⊤} p _{k}}{∥ p _{k} ∥ ^{2}} = \frac{1 - c _{2}}{L} \frac{- g _{k}^{⊤} p _{k}}{∥ p _{k} ∥ ^{2}} .

This is a lower bound on the step length forced by the curvature condition. Now insert it into the Armijo decrease. Sufficient decrease gives

f (x_{k + 1}) \leq f (x_{k}) + c_{1} α_{k} g_{k}^{⊤} p_{k} = f (x_{k}) - c_{1} α_{k} (- g_{k}^{⊤} p_{k}),

and using the step-length bound (and $- g_{k}^{⊤} p_{k} > 0$ ),

f (x_{k + 1}) \leq f (x_{k}) - c_{1} \frac{1 - c _{2}}{L} \frac{( g _{k}^{⊤} p _{k} ) ^{2}}{∥ p _{k} ∥ ^{2}} .

Write $c = c_{1} (1 - c_{2}) / L > 0$ . By the definition of $θ_{k}$ , $(g_{k}^{⊤} p_{k})^{2} /∥ p_{k} ∥^{2} = cos^{2} θ_{k} ∥ g_{k} ∥^{2}$ , hence

f (x_{k + 1}) \leq f (x_{k}) - c cos^{2} θ_{k} ∥ g_{k} ∥^{2} .

Summing from $0$ to $N$ telescopes the left side: $f (x_{N + 1}) \leq f (x_{0}) - c \sum_{k = 0}^{N} cos^{2} θ_{k} ∥ g_{k} ∥^{2}$ . Since $f$ is bounded below, $f (x_{0}) - f (x_{N + 1})$ is bounded above uniformly in $N$ , so the partial sums $\sum_{k = 0}^{N} cos^{2} θ_{k} ∥ g_{k} ∥^{2}$ are bounded; being nonnegative, the series converges. $□$

Bridge. This summability is the foundational reason a purely local acceptance test produces a global guarantee, and it builds toward the angle-condition corollary that opens the Advanced results: if $cos θ_{k} \geq δ > 0$ for all $k$ , the converging series forces $∥ g_{k} ∥^{2} \to 0$ , so $\nabla f (x_{k}) \to 0$ and every limit point is stationary. The mechanism is exactly the descent lemma of multivariable Taylor expansion 02.05.05 married to the curvature-forced lower bound on $α_{k}$ — the two Wolfe conditions are dual, sufficient decrease bounding progress from above and curvature bounding the step from below, and putting these together is what makes the per-step gain $cos^{2} θ_{k} ∥ g_{k} ∥^{2}$ both real and summable. This is exactly the quantity the central insight of the chapter rests on: steepest descent takes $cos θ_{k} = 1$ and inherits convergence directly, while Newton 44.03.03 and quasi-Newton 44.03.04 methods must keep their directions angle-bounded to ride the same theorem, and the result appears again in the global-convergence analysis of nonlinear conjugate gradient 44.03.06 where maintaining $cos θ_{k} \geq δ$ is the delicate point.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Show that backtracking from $\overset{α}{ˉ}$ with contraction $ρ \in (0, 1)$ terminates in finitely many steps and returns a step length $α_{k} \geq min {\overset{α}{ˉ}, ρ α_{A}}$ , where $α_{A}$ is the largest step for which Armijo holds.

Hint

Backtracking accepts the first $ρ^{j} \overset{α}{ˉ}$ satisfying Armijo. Use that Armijo holds on $(0, α_{A}]$ for a quadratic-like decrease, and that the previous trial $ρ^{j - 1} \overset{α}{ˉ}$ failed.

Answer

By Exercise 2, Armijo holds for all small enough $α$ , so some power $ρ^{j} \overset{α}{ˉ}$ satisfies it; the loop halts at the first such $j$ , finitely many steps since $ρ^{j} \overset{α}{ˉ} \to 0$ . If $\overset{α}{ˉ}$ itself passes ( $j = 0$ ) then $α_{k} = \overset{α}{ˉ}$ . Otherwise the accepted value is $α_{k} = ρ^{j} \overset{α}{ˉ}$ where $ρ^{j - 1} \overset{α}{ˉ}$ was rejected, meaning $ρ^{j - 1} \overset{α}{ˉ} > α_{A}$ (Armijo fails above the acceptance threshold), so $α_{k} = ρ \cdot ρ^{j - 1} \overset{α}{ˉ} > ρ α_{A}$ . In either case $α_{k} \geq min {\overset{α}{ˉ}, ρ α_{A}}$ . This uniform lower bound is what lets backtracking-only methods (Armijo without an explicit curvature test) inherit a Zoutendijk-type guarantee. Full credit for finiteness plus the $ρ α_{A}$ bound.

Exercise 4 (medium, numeric).

For $f (x_{1}, x_{2}) = x_{1}^{2} + 4 x_{2}^{2}$ at $x = (1, 1)$ with $p = - \nabla f = (- 2, - 8)$ , find the interval of step lengths $α$ satisfying the strong Wolfe conditions with $c_{1} = 0.1$ , $c_{2} = 0.9$ . Report the exact-minimiser step $α^{⋆}$ and confirm it lies in the interval.

Hint

$ϕ (α) = (1 - 2 α)^{2} + 4 (1 - 8 α)^{2}$ ; minimise to get $α^{⋆} = (g^{⊤} g) / (g^{⊤} \nabla^{2} f g)$ with $g = (2, 8)$ , $\nabla^{2} f = diag (2, 8)$ .

Answer

The exact minimiser of the quadratic $ϕ$ is $α^{⋆} = (g^{⊤} g) / (g^{⊤} H g)$ with $g = (2, 8)$ , $H = diag (2, 8)$ : $g^{⊤} g = 4 + 64 = 68$ , $g^{⊤} H g = 2 \cdot 4 + 8 \cdot 64 = 8 + 512 = 520$ , so $α^{⋆} = 68/520 = 0.13077$ . At $α^{⋆}$ the slope $ϕ^{'} (α^{⋆}) = 0$ , which satisfies the strong curvature bound $∣ ϕ^{'} (α) ∣ \leq 0.9 \cdot 68 = 61.2$ with room to spare, and the strong-Wolfe curvature condition holds on the interval where $∣ ϕ^{'} (α) ∣ \leq 61.2$ , i.e. where $∣ - 68 + 520 α ∣ \leq 61.2$ , giving $0.01308 \leq α \leq 0.24862$ . Armijo holds up to $α = 0.2615$ (solve $ϕ (α) \leq 5 - 6.8 α$ ), so the strong-Wolfe interval is about $[0.0131, 0.2486]$ , which contains $α^{⋆} = 0.1308$ . Full credit for $α^{⋆} \approx 0.131$ inside the curvature interval.

Exercise 5 (medium, symbolic).

Prove that on a strongly convex quadratic $f (x) = \frac{1}{2} x^{⊤} A x - b^{⊤} x$ ( $A ≻ 0$ ), the steepest-descent direction $p = - g$ has $cos θ = 1$ , and deduce from Zoutendijk's theorem that steepest descent with Wolfe steps satisfies $g_{k} \to 0$ .

Hint

With $p = - g$ , compute $cos θ = - g^{⊤} p / (∥ g ∥∥ p ∥)$ . Then a constant $cos θ = 1 \geq δ$ is the angle condition.

Answer

With $p_{k} = - g_{k}$ , $- g_{k}^{⊤} p_{k} = g_{k}^{⊤} g_{k} = ∥ g_{k} ∥^{2}$ and $∥ p_{k} ∥ = ∥ g_{k} ∥$ , so $cos θ_{k} = ∥ g_{k} ∥^{2} / (∥ g_{k} ∥ \cdot ∥ g_{k} ∥) = 1$ at every step. The gradient $\nabla f (x) = A x - b$ is Lipschitz with constant $L = ∥ A ∥$ , and $f$ is bounded below ( $A ≻ 0$ ). Zoutendijk's theorem gives $\sum_{k} cos^{2} θ_{k} ∥ g_{k} ∥^{2} = \sum_{k} ∥ g_{k} ∥^{2} < \infty$ , so $∥ g_{k} ∥^{2} \to 0$ , hence $g_{k} \to 0$ and $x_{k} \to x_{⋆} = A^{- 1} b$ . The angle condition is satisfied with $δ = 1$ , the best possible. Full credit for $cos θ_{k} = 1$ and the summability conclusion.

Exercise 6 (hard, symbolic).

Establish the existence of Wolfe step lengths: if $ϕ (α) = f (x_{k} + α p_{k})$ is continuously differentiable, $ϕ^{'} (0) < 0$ , and $ϕ$ is bounded below for $α > 0$ , then for any $0 < c_{1} < c_{2} < 1$ there is an open interval of $α$ satisfying both Wolfe conditions.

Hint

The Armijo line $ℓ (α) = ϕ (0) + c_{1} α ϕ^{'} (0)$ is unbounded below but $ϕ$ is bounded below, so they cross at a smallest $α^{'} > 0$ . Apply the mean value theorem on $[0, α^{'}]$ .

Answer

Since $ϕ$ is bounded below and the affine function $ℓ (α) = ϕ (0) + c_{1} α ϕ^{'} (0)$ decreases without bound (as $ϕ^{'} (0) < 0$ ), the continuous function $ϕ (α) - ℓ (α)$ is positive for small $α$ (it equals $0$ at $α = 0$ with derivative $(1 - c_{1}) ϕ^{'} (0) < 0$ , so $ϕ < ℓ$ initially) and eventually $ϕ > ℓ$ ; let $α^{'} > 0$ be the smallest crossing, so $ϕ (α^{'}) = ℓ (α^{'}) = ϕ (0) + c_{1} α^{'} ϕ^{'} (0)$ and Armijo holds on $(0, α^{'}]$ . By the mean value theorem there is $α^{''} \in (0, α^{'})$ with $ϕ^{'} (α^{''}) = (ϕ (α^{'}) - ϕ (0)) / α^{'} = c_{1} ϕ^{'} (0)$ . Since $c_{1} < c_{2}$ and $ϕ^{'} (0) < 0$ , $ϕ^{'} (α^{''}) = c_{1} ϕ^{'} (0) > c_{2} ϕ^{'} (0)$ , so the curvature condition holds at $α^{''}$ . As $α^{''} < α^{'}$ , Armijo holds there too, and by continuity of $ϕ^{'}$ both conditions hold on an open interval around $α^{''}$ . Because $ϕ^{'} (α^{''}) < 0$ , the strong Wolfe condition $∣ ϕ^{'} (α^{''}) ∣ \leq c_{2} ∣ ϕ^{'} (0) ∣$ also holds there. Full credit for the crossing argument plus the mean-value step.

Exercise 7 (hard, symbolic).

Derive the steepest-descent linear rate on a quadratic: for $f (x) = \frac{1}{2} x^{⊤} A x - b^{⊤} x$ with $A ≻ 0$ , exact line search gives $∥ x_{k + 1} - x_{⋆} ∥_{A}^{2} \leq ((κ - 1) / (κ + 1))^{2} ∥ x_{k} - x_{⋆} ∥_{A}^{2}$ with $κ = λ_{m a x} / λ_{m i n}$ .

Hint

Let $e_{k} = x_{k} - x_{⋆}$ , $g_{k} = A e_{k}$ . With exact step $α_{k} = g_{k}^{⊤} g_{k} / (g_{k}^{⊤} A g_{k})$ , expand $∥ e_{k + 1} ∥_{A}^{2} = ∥ e_{k} ∥_{A}^{2} (1 - (g_{k}^{⊤} g_{k})^{2} / ((g_{k}^{⊤} A g_{k}) (g_{k}^{⊤} A^{- 1} g_{k})))$ and apply the Kantorovich inequality.

Answer

Write $e_{k} = x_{k} - x_{⋆}$ so $g_{k} = \nabla f (x_{k}) = A e_{k}$ and $∥ e_{k} ∥_{A}^{2} = e_{k}^{⊤} A e_{k} = g_{k}^{⊤} A^{- 1} g_{k}$ . Exact line search along $- g_{k}$ uses $α_{k} = (g_{k}^{⊤} g_{k}) / (g_{k}^{⊤} A g_{k})$ , and a direct expansion gives

∥ e_{k + 1} ∥_{A}^{2} = ∥ e_{k} ∥_{A}^{2} (1 - \frac{( g _{k}^{⊤} g _{k} ) ^{2}}{( g _{k}^{⊤} A g _{k} ) ( g _{k}^{⊤} A ^{- 1} g _{k} )}) .

The Kantorovich inequality states that for $A ≻ 0$ and any $v \neq = 0$ ,

\frac{( v ^{⊤} v ) ^{2}}{( v ^{⊤} A v ) ( v ^{⊤} A ^{- 1} v )} \geq \frac{4 λ _{m a x} λ _{m i n}}{( λ _{m a x} + λ _{m i n} ) ^{2}} .

Substituting with $v = g_{k}$ ,

∥ e_{k + 1} ∥_{A}^{2} \leq ∥ e_{k} ∥_{A}^{2} (1 - \frac{4 λ _{m a x} λ _{m i n}}{( λ _{m a x} + λ _{m i n} ) ^{2}}) = ∥ e_{k} ∥_{A}^{2} \frac{( λ _{m a x} - λ _{m i n} ) ^{2}}{( λ _{m a x} + λ _{m i n} ) ^{2}} = ∥ e_{k} ∥_{A}^{2} (\frac{κ - 1}{κ + 1})^{2},

dividing numerator and denominator by $λ_{m i n}$ . The rate is linear with factor $((κ - 1) / (κ + 1))^{2}$ ; for large $κ$ this is $\approx 1 - 4/ κ$ , so the iteration count to fixed accuracy grows like $κ$ . Full credit for the Kantorovich substitution and the final factor.

Advanced results Master

The line-search framework is the iteration $x_{k + 1} = x_{k} + α_{k} p_{k}$ with a descent direction and a Wolfe-acceptable step, and the results below convert Zoutendijk's summability into convergence, exhibit the sharp rate of the canonical method, and locate the framework's limits — where the angle condition fails and where the local rate is governed by curvature rather than by the line search.

Theorem 1 (global convergence under the angle condition). Let the hypotheses of Zoutendijk's theorem hold, and suppose the search directions satisfy the angle condition $cos θ_{k} \geq δ > 0$ for all $k$ . Then $lim_{k \to \infty} ∥\nabla f (x_{k}) ∥ = 0$ , so every limit point of ${x_{k}}$ is stationary. Indeed Zoutendijk gives $\sum_{k} cos^{2} θ_{k} ∥ g_{k} ∥^{2} < \infty$ , and $cos^{2} θ_{k} \geq δ^{2}$ forces $\sum_{k} ∥ g_{k} ∥^{2} < \infty$ , whence $∥ g_{k} ∥ \to 0$ . For a convex $f$ a stationary point is a global minimiser, and for strongly convex $f$ the unique minimiser is reached; without convexity the guarantee is only stationarity, which is the honest ceiling of first-order line-search theory ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Theorem 2 (steepest descent: sharp linear rate and its condition-number dependence). For $f$ twice continuously differentiable with $\nabla^{2} f (x_{⋆}) = A ≻ 0$ at a strict local minimiser, steepest descent with exact line search converges linearly with

\frac{f ( x _{k + 1} ) - f ( x _{⋆} )}{f ( x _{k} ) - f ( x _{⋆} )} \to (\frac{κ - 1}{κ + 1})^{2}, κ = \frac{λ _{m a x} ( A )}{λ _{m i n} ( A )},

and the bound is attained on the worst-case quadratic, where the iterates zig-zag between the two extreme eigendirections. The same factor governs steepest descent with Wolfe (inexact) steps up to constants. The rate degrades to $1$ as $κ \to \infty$ : the per-iteration progress is $O (1/ κ)$ , the structural reason steepest descent is abandoned for the curvature-aware methods that follow. Kantorovich's inequality is the exact tool that makes the factor sharp ^{[Bertsekas, D. P. — Nonlinear Programming (3rd ed.)]}.

Theorem 3 (Goldstein conditions and their relation to Wolfe). The Goldstein conditions $f_{k} + (1 - c) α g_{k}^{⊤} p_{k} \leq f (x_{k} + α p_{k}) \leq f_{k} + c α g_{k}^{⊤} p_{k}$ with $c \in (0, \frac{1}{2})$ also admit a step-length interval and yield a Zoutendijk-type sum, using only function values — no gradient at the trial point — which suited early implementations. Their defect is that the lower Goldstein bound can exclude the exact one-dimensional minimiser, whereas the Wolfe curvature condition never does; for that reason Wolfe is preferred in quasi-Newton methods where the curvature condition additionally guarantees that the secant pair $(s_{k}, y_{k}) = (x_{k + 1} - x_{k}, g_{k + 1} - g_{k})$ satisfies $s_{k}^{⊤} y_{k} > 0$ , the positivity that keeps the BFGS update positive-definite ^{[Dennis, J. E. & Schnabel, R. B. — Numerical Methods for Unconstrained Optimization and Nonlinear Equations]}.

Theorem 4 (the curvature condition and quasi-Newton positivity). Under the curvature condition $g_{k + 1}^{⊤} p_{k} \geq c_{2} g_{k}^{⊤} p_{k}$ , the curvature pair satisfies

s_{k}^{⊤} y_{k} = α_{k} p_{k}^{⊤} (g_{k + 1} - g_{k}) = α_{k} (p_{k}^{⊤} g_{k + 1} - p_{k}^{⊤} g_{k}) \geq α_{k} (c_{2} - 1) p_{k}^{⊤} g_{k} = α_{k} (1 - c_{2}) (- p_{k}^{⊤} g_{k}) > 0,

since $α_{k} > 0$ , $c_{2} < 1$ , and $p_{k}^{⊤} g_{k} < 0$ . This single inequality is why the Wolfe conditions are the standard acceptance test for quasi-Newton methods: it certifies that the Broyden-Fletcher-Goldfarb-Shanno (BFGS) and Davidon-Fletcher-Powell (DFP) updates inherit positive-definiteness from one iterate to the next, so the generated directions stay descent directions automatically and the angle condition is maintained without an explicit safeguard. The local superlinear rate of these methods then takes over from the line search once the iterates are near the minimiser ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Synthesis. Line search is one framework — descent direction plus Wolfe-acceptable step — and Zoutendijk's summability $\sum_{k} cos^{2} θ_{k} ∥ g_{k} ∥^{2} < \infty$ is the single invariant from which its entire global theory descends, the foundational reason a local two-line acceptance test yields convergence to stationary points. The central insight is the division of labour the framework enforces: the line search owns *globalisation* — it drives $∥\nabla f_{k} ∥ \to 0$ from any start, provided the directions stay angle-bounded — while the *local rate* is owned by the direction, not the step. This is exactly why steepest descent, with the best possible $cos θ_{k} = 1$ , still converges only linearly with the condition-number factor $((κ - 1) / (κ + 1))^{2}$ : the line search cannot repair a poorly chosen direction, and Kantorovich's inequality makes the penalty sharp. The curvature condition is dual to sufficient decrease — one forbids too-short steps, the other too-long — and putting these together produces both the step-length lower bound that powers Zoutendijk and the secant positivity $s_{k}^{⊤} y_{k} > 0$ that keeps quasi-Newton updates definite. The bridge is therefore explicit: the same Wolfe test that globalises steepest descent here generalises to certify the descent property of Newton 44.03.03, the positive-definiteness of BFGS 44.03.04, and the restart logic of nonlinear conjugate gradient 44.03.06, and trust-region methods 44.03.05 arise precisely by replacing the line search with a constrained model minimisation when even an angle-bounded direction is unreliable.

Full proof set Master

Proposition 1 (Zoutendijk summability). Under the hypotheses of the Key theorem — $f \in C^{1}$ bounded below, $\nabla f$ Lipschitz of constant $L$ , descent directions, Wolfe steps with $0 < c_{1} < c_{2} < 1$ — one has $\sum_{k} cos^{2} θ_{k} ∥ g_{k} ∥^{2} < \infty$ .

Proof. The curvature condition gives $(g_{k + 1} - g_{k})^{⊤} p_{k} \geq (c_{2} - 1) g_{k}^{⊤} p_{k} > 0$ . The Lipschitz bound and Cauchy-Schwarz give $(g_{k + 1} - g_{k})^{⊤} p_{k} \leq ∥ g_{k + 1} - g_{k} ∥∥ p_{k} ∥ \leq L α_{k} ∥ p_{k} ∥^{2}$ . Hence $α_{k} \geq (1 - c_{2}) (- g_{k}^{⊤} p_{k}) / (L ∥ p_{k} ∥^{2})$ . Substituting into the Armijo decrease $f (x_{k + 1}) \leq f (x_{k}) + c_{1} α_{k} g_{k}^{⊤} p_{k} = f (x_{k}) - c_{1} α_{k} (- g_{k}^{⊤} p_{k})$ yields

f (x_{k + 1}) \leq f (x_{k}) - \frac{c _{1} ( 1 - c _{2} )}{L} \frac{( g _{k}^{⊤} p _{k} ) ^{2}}{∥ p _{k} ∥ ^{2}} = f (x_{k}) - \frac{c _{1} ( 1 - c _{2} )}{L} cos^{2} θ_{k} ∥ g_{k} ∥^{2} .

Telescoping and using the lower bound on $f$ bounds the nonnegative partial sums, so the series converges. $□$

Proposition 2 (angle-condition global convergence). If additionally $cos θ_{k} \geq δ > 0$ for all $k$ , then $\nabla f (x_{k}) \to 0$ .

Proof. From Proposition 1, $\sum_{k} cos^{2} θ_{k} ∥ g_{k} ∥^{2} < \infty$ . The term bound $cos^{2} θ_{k} ∥ g_{k} ∥^{2} \geq δ^{2} ∥ g_{k} ∥^{2}$ gives $δ^{2} \sum_{k} ∥ g_{k} ∥^{2} \leq \sum_{k} cos^{2} θ_{k} ∥ g_{k} ∥^{2} < \infty$ , so $\sum_{k} ∥ g_{k} ∥^{2} < \infty$ and the summand $∥ g_{k} ∥^{2} \to 0$ . Thus $∥\nabla f (x_{k}) ∥ \to 0$ ; any convergent subsequence $x_{k_{j}} \to \overset{x}{ˉ}$ has, by continuity of $\nabla f$ , $\nabla f (\overset{x}{ˉ}) = 0$ , so every limit point is stationary. $□$

Proposition 3 (existence of a Wolfe interval). If $ϕ (α) = f (x_{k} + α p_{k})$ is $C^{1}$ , $ϕ^{'} (0) < 0$ , and $ϕ$ is bounded below on $α \geq 0$ , then for any $0 < c_{1} < c_{2} < 1$ the set of $α > 0$ satisfying both the Armijo and curvature conditions contains a nonempty open interval; the strong Wolfe conditions hold there too.

Proof. Let $ℓ (α) = ϕ (0) + c_{1} α ϕ^{'} (0)$ . Since $ϕ^{'} (0) < 0$ , $ℓ$ is decreasing and unbounded below, while $ϕ$ is bounded below, so the continuous map $α \mapsto ϕ (α) - ℓ (α)$ , zero at $α = 0$ with negative one-sided derivative $(1 - c_{1}) ϕ^{'} (0)$ , is negative for small $α > 0$ and becomes positive; let $α^{'}$ be the least positive root, so $ϕ (α^{'}) = ℓ (α^{'})$ and Armijo holds on $(0, α^{'}]$ . The mean value theorem provides $α^{''} \in (0, α^{'})$ with

ϕ^{'} (α^{''}) = \frac{ϕ ( α ^{'} ) - ϕ ( 0 )}{α ^{'}} = c_{1} ϕ^{'} (0) .

Because $c_{2} > c_{1}$ and $ϕ^{'} (0) < 0$ , $ϕ^{'} (α^{''}) = c_{1} ϕ^{'} (0) > c_{2} ϕ^{'} (0)$ , so curvature holds at $α^{''}$ ; since $ϕ^{'} (α^{''}) = c_{1} ϕ^{'} (0) < 0$ , also $∣ ϕ^{'} (α^{''}) ∣ = c_{1} ∣ ϕ^{'} (0) ∣ < c_{2} ∣ ϕ^{'} (0) ∣$ , the strong form. As $α^{''} < α^{'}$ , Armijo holds at $α^{''}$ , and continuity of $ϕ^{'}$ and $ϕ - ℓ$ extends both conditions to an open interval about $α^{''}$ . $□$

Proposition 4 (backtracking terminates with a useful step). Backtracking from $\overset{α}{ˉ}$ with contraction $ρ \in (0, 1)$ and Armijo constant $c_{1}$ halts after finitely many reductions and returns $α_{k}$ with $α_{k} \geq min {\overset{α}{ˉ}, ρ α_{A}}$ , where $α_{A} = sup {α : Armijo holds on (0, α]}$ .

Proof. By the first-order expansion $ϕ (α) - ϕ (0) - c_{1} α ϕ^{'} (0) = (1 - c_{1}) ϕ^{'} (0) α + o (α)$ with $(1 - c_{1}) ϕ^{'} (0) < 0$ , the Armijo inequality holds for all small $α$ , so some $ρ^{j} \overset{α}{ˉ}$ satisfies it and the loop halts; finiteness follows from $ρ^{j} \overset{α}{ˉ} \to 0$ . If $j = 0$ , $α_{k} = \overset{α}{ˉ}$ . If $j \geq 1$ , the prior trial $ρ^{j - 1} \overset{α}{ˉ}$ failed Armijo, so $ρ^{j - 1} \overset{α}{ˉ} > α_{A}$ , giving $α_{k} = ρ^{j} \overset{α}{ˉ} = ρ \cdot ρ^{j - 1} \overset{α}{ˉ} > ρ α_{A}$ . Hence $α_{k} \geq min {\overset{α}{ˉ}, ρ α_{A}}$ , a positive lower bound that, combined with a uniform lower bound on $α_{A}$ from the Lipschitz constant, yields a Zoutendijk sum for backtracking-only methods. $□$

Proposition 5 (steepest-descent linear rate via Kantorovich). For $f (x) = \frac{1}{2} x^{⊤} A x - b^{⊤} x$ with $A ≻ 0$ , steepest descent with exact line search satisfies $∥ e_{k + 1} ∥_{A}^{2} \leq ((κ - 1) / (κ + 1))^{2} ∥ e_{k} ∥_{A}^{2}$ , $e_{k} = x_{k} - x_{⋆}$ , $κ = λ_{m a x} / λ_{m i n}$ .

Proof. With $g_{k} = A e_{k}$ and exact step $α_{k} = (g_{k}^{⊤} g_{k}) / (g_{k}^{⊤} A g_{k})$ , the energy-norm recursion expands to

∥ e_{k + 1} ∥_{A}^{2} = ∥ e_{k} ∥_{A}^{2} (1 - \frac{( g _{k}^{⊤} g _{k} ) ^{2}}{( g _{k}^{⊤} A g _{k} ) ( g _{k}^{⊤} A ^{- 1} g _{k} )}),

using $∥ e_{k} ∥_{A}^{2} = g_{k}^{⊤} A^{- 1} g_{k}$ . The Kantorovich inequality bounds the ratio below by $4 λ_{m a x} λ_{m i n} / (λ_{m a x} + λ_{m i n})^{2}$ , so the contraction factor is at most $1 - 4 λ_{m a x} λ_{m i n} / (λ_{m a x} + λ_{m i n})^{2} = (λ_{m a x} - λ_{m i n})^{2} / (λ_{m a x} + λ_{m i n})^{2} = ((κ - 1) / (κ + 1))^{2}$ . $□$

Proposition 6 (curvature condition forces $s_{k}^{⊤} y_{k} > 0$ ). Under the curvature condition with $c_{2} < 1$ , the secant pair $s_{k} = x_{k + 1} - x_{k}$ , $y_{k} = g_{k + 1} - g_{k}$ satisfies $s_{k}^{⊤} y_{k} > 0$ .

Proof. Since $s_{k} = α_{k} p_{k}$ with $α_{k} > 0$ , $s_{k}^{⊤} y_{k} = α_{k} p_{k}^{⊤} (g_{k + 1} - g_{k})$ . The curvature condition gives $p_{k}^{⊤} g_{k + 1} \geq c_{2} p_{k}^{⊤} g_{k}$ , so $p_{k}^{⊤} (g_{k + 1} - g_{k}) \geq (c_{2} - 1) p_{k}^{⊤} g_{k} = (1 - c_{2}) (- p_{k}^{⊤} g_{k}) > 0$ because $c_{2} < 1$ and $p_{k}^{⊤} g_{k} < 0$ . Multiplying by $α_{k} > 0$ gives $s_{k}^{⊤} y_{k} > 0$ . $□$

Connections Master

Convex functions and their second-order conditions 44.01.01 supply the structural guarantee that converts the line-search stationarity result into optimality: Zoutendijk's theorem alone delivers only $\nabla f (x_{k}) \to 0$ , but when $f$ is convex a stationary point is a global minimiser, and when $f$ is strongly convex the unique minimiser is reached at the linear rate of Theorem 2. The strong-convexity modulus and the Hessian condition number $κ$ that govern the steepest-descent factor $((κ - 1) / (κ + 1))^{2}$ are exactly the curvature data that unit formalises, so the rate theory of line search is the quantitative shadow of the convexity theory.
Multivariable Taylor expansion and the test for extrema 02.05.05 is the analytic engine of every estimate here: the descent lemma $f (x + α p) \leq f (x) + α g^{⊤} p + \frac{1}{2} L α^{2} ∥ p ∥^{2}$ that underlies sufficient decrease, the mean value theorem step in the Wolfe-existence proof, and the second-order expansion that produces the asymptotic steepest-descent rate all come from that unit's Taylor machinery. The first-order stationarity condition $\nabla f (x_{⋆}) = 0$ that line search drives toward is the necessary condition for an extremum established there.
Newton's method 44.03.03, quasi-Newton (BFGS/DFP) methods 44.03.04, trust-region methods 44.03.05, and nonlinear conjugate gradient 44.03.06 are the consumers of this framework: each chooses a search direction and then relies on the Wolfe line search of this unit to globalise it. The curvature condition's guarantee $s_{k}^{⊤} y_{k} > 0$ is precisely what keeps the BFGS update positive-definite, the angle condition is the hypothesis Newton and quasi-Newton directions must verify to inherit Zoutendijk convergence, and the line-search-versus-trust-region split is the chapter's two answers to the same globalisation problem. The condition-number-dependent rate of steepest descent here is the baseline these curvature-aware methods improve upon.

Historical & philosophical context Master

The idea of minimising a function by repeatedly stepping along the negative gradient goes back to Augustin-Louis Cauchy's 1847 note Méthode générale pour la résolution des systèmes d'équations simultanées, where he proposed following the steepest descent of a sum of squares to solve nonlinear systems ^{[Cauchy 1847]}. The method was studied as a practical algorithm only in the twentieth century, and its slow, zig-zagging behaviour on ill-conditioned problems — quantified by the $((κ - 1) / (κ + 1))^{2}$ factor and Kantorovich's inequality — motivated the search for curvature-aware alternatives.

The modern theory of inexact line searches crystallised around three acceptance rules. Larry Armijo's 1966 paper introduced the sufficient-decrease condition that bears his name, proving convergence of gradient methods under a step-reduction rule ^{[Armijo 1966]}. A. A. Goldstein proposed his two-sided bound in the same period to keep steps from being too short without a trial gradient. Philip Wolfe's 1969 paper Convergence conditions for ascent methods added the curvature condition, giving the pair now called the Wolfe conditions and isolating the property that makes them ideal for quasi-Newton methods ^{[Wolfe 1969]}. The global-convergence analysis that ties these acceptance rules to stationarity through the summability of $cos^{2} θ_{k} ∥ g_{k} ∥^{2}$ is due to Guus Zoutendijk, whose 1970 contribution made the angle condition the organising hypothesis of first-order convergence theory ^{[Zoutendijk 1970]}. The synthesis presented in Nocedal and Wright's textbook is the form in which the framework is now taught and implemented.

Bibliography Master

@book{nocedalwright2006,
  author    = {Nocedal, Jorge and Wright, Stephen J.},
  title     = {Numerical Optimization},
  edition   = {2},
  series    = {Springer Series in Operations Research and Financial Engineering},
  publisher = {Springer},
  year      = {2006}
}

@book{dennisschnabel1996,
  author    = {Dennis, John E. and Schnabel, Robert B.},
  title     = {Numerical Methods for Unconstrained Optimization and Nonlinear Equations},
  series    = {Classics in Applied Mathematics},
  volume    = {16},
  publisher = {SIAM},
  year      = {1996},
  note      = {Reprint of the 1983 Prentice-Hall edition}
}

@book{bertsekas2016,
  author    = {Bertsekas, Dimitri P.},
  title     = {Nonlinear Programming},
  edition   = {3},
  publisher = {Athena Scientific},
  year      = {2016}
}

@article{armijo1966,
  author  = {Armijo, Larry},
  title   = {Minimization of functions having Lipschitz continuous first partial derivatives},
  journal = {Pacific Journal of Mathematics},
  volume  = {16},
  number  = {1},
  year    = {1966},
  pages   = {1--3}
}

@article{wolfe1969,
  author  = {Wolfe, Philip},
  title   = {Convergence conditions for ascent methods},
  journal = {SIAM Review},
  volume  = {11},
  number  = {2},
  year    = {1969},
  pages   = {226--235}
}

@incollection{zoutendijk1970,
  author    = {Zoutendijk, Guus},
  title     = {Nonlinear programming, computational methods},
  booktitle = {Integer and Nonlinear Programming},
  editor    = {Abadie, J.},
  publisher = {North-Holland},
  address   = {Amsterdam},
  year      = {1970},
  pages     = {37--86}
}

@article{cauchy1847,
  author  = {Cauchy, Augustin-Louis},
  title   = {M\'{e}thode g\'{e}n\'{e}rale pour la r\'{e}solution des syst\`{e}mes d'\'{e}quations simultan\'{e}es},
  journal = {Comptes Rendus de l'Acad\'{e}mie des Sciences},
  volume  = {25},
  year    = {1847},
  pages   = {536--538}
}

Prerequisites

44.01.01
02.05.05

Tier anchors

beginner: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §3.1 (the descent-direction / step-length framework, the geometric meaning of the sufficient-decrease and curvature pictures); Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §9.2 (backtracking line search as a practical recipe)
intermediate: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §3.1-3.2 (the Armijo sufficient-decrease condition, the curvature condition, the strong and weak Wolfe conditions, the Goldstein conditions, the existence theorem for Wolfe step lengths, and backtracking); Dennis & Schnabel 1996 Numerical Methods for Unconstrained Optimization and Nonlinear Equations (SIAM) §6.3
master: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §3.2-3.3 (Zoutendijk's theorem, the angle condition, global convergence of line-search methods to stationary points, and the linear convergence rate of steepest descent with the condition-number-dependent constant); Zoutendijk 1970 Nonlinear programming, computational methods (in Abadie, ed., North-Holland); Bertsekas 2016 Nonlinear Programming 3e (Athena Scientific) §1.2

References

Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.) · Springer Series in Operations Research and Financial Engineering (2006). Chapter 3 'Line Search Methods', §3.1-3.3: the generic line-search iteration $x_{k + 1} = x_{k} + α_{k} p_{k}$ with a descent direction $p_{k}$ ( $\nabla f (x_{k})^{⊤} p_{k} < 0$ ); the Armijo sufficient-decrease condition $f (x_{k} + α p_{k}) \leq f (x_{k}) + c_{1} α \nabla f (x_{k})^{⊤} p_{k}$ ; the curvature condition $\nabla f (x_{k} + α p_{k})^{⊤} p_{k} \geq c_{2} \nabla f (x_{k})^{⊤} p_{k}$ with $0 < c_{1} < c_{2} < 1$ ; the (weak and strong) Wolfe conditions and the Goldstein conditions $f (x_{k}) + (1 - c) α \nabla f_{k}^{⊤} p_{k} \leq f (x_{k} + α p_{k}) \leq f (x_{k}) + c α \nabla f_{k}^{⊤} p_{k}$ ; the existence lemma (Lemma 3.1) that step lengths satisfying the Wolfe conditions exist whenever $f$ is bounded below along the ray and continuously differentiable; the backtracking line search that needs only Armijo; Zoutendijk's theorem $\sum_{k} cos^{2} θ_{k} ∥\nabla f_{k} ∥^{2} < \infty$ under a Lipschitz gradient and the Wolfe conditions; the resulting global convergence $\nabla f_{k} \to 0$ under the angle condition $cos θ_{k} \geq δ > 0$ ; and the linear convergence of steepest descent on a strongly convex quadratic with factor $((κ - 1) / (κ + 1))^{2}$ in the energy norm, $κ$ the condition number of the Hessian.
Dennis, J. E. & Schnabel, R. B. — Numerical Methods for Unconstrained Optimization and Nonlinear Equations · SIAM Classics in Applied Mathematics 16 (1996, reprint of the 1983 Prentice-Hall edition). §6.3 develops globally convergent modifications of Newton's method through line searches: the $α$ -condition (Armijo / sufficient decrease) and a $β$ -condition (curvature) ensuring the step is neither too long nor too short, the backtracking framework with quadratic and cubic interpolation models of $ϕ (α) = f (x_{k} + α p_{k})$ to choose trial step lengths, and the global-convergence theorem that the gradients tend to zero when descent directions are bounded away from orthogonality to $- \nabla f$ . The treatment emphasises the affine model $m_{k} (α) = f_{k} + c_{1} α \nabla f_{k}^{⊤} p_{k}$ as the acceptance threshold and the practical safeguards (step-length bounds, interpolation) that make the theory implementable.
Bertsekas, D. P. — Nonlinear Programming (3rd ed.) · Athena Scientific, 3rd edition (2016). §1.2 'Gradient Methods — Convergence' presents the gradient iteration $x_{k + 1} = x_{k} + α_{k} d_{k}$ with gradient-related directions and the stepsize rules (constant, diminishing, minimisation rule, limited minimisation, Armijo / successive reduction), and proves the stationarity result that every limit point of the sequence is stationary under the Armijo rule with gradient-related directions. The convergence-rate analysis for steepest descent on a positive-definite quadratic gives the geometric factor governed by the ratio of extreme eigenvalues of the Hessian, the condition number, and Kantorovich's inequality is the sharp tool there; the same section frames the angle (gradient-relatedness) condition that this unit's Zoutendijk theorem makes quantitative.

Estimated time

beginner: 18m
intermediate: 48m
master: 90m