44.03.06 · optimization-control / unconstrained-optimization

Nonlinear Conjugate Gradient Methods: Fletcher-Reeves and Polak-Ribière

shipped3 tiersLean: none

Anchor (Master): Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §5.2 and the global-convergence analysis of Fletcher-Reeves under strong Wolfe (the Al-Baali descent lemma) together with the PR cycling example and the PR+ fix; Hager & Zhang 2006 A survey of nonlinear conjugate gradient methods (Pacific J. Optim. 2, 35-58) (the unified $β_{k}$ family, descent and global-convergence theory, and the CG_DESCENT line search); Dai & Yuan 1999 A nonlinear conjugate gradient method with a strong global convergence property (SIAM J. Optim. 10, 177-182)

Intuition Beginner

The conjugate gradient idea was built for a perfect bowl: a valley whose shape comes from a symmetric system of equations, where you can choose each downhill direction so it never spoils the progress of the earlier ones, and you reach the bottom in a fixed small number of clever steps. Most real problems are not perfect bowls. The valley bends, the steepness changes from place to place, and there is no single matrix describing the whole landscape. Nonlinear conjugate gradient is the answer to a simple question: can the same cheap, low-memory trick still help when the valley is a general curved surface?

The plan adapts in two ways. First, since there is no fixed matrix to read the slope from, you measure the slope freshly at each new spot — that is what the gradient gives you. Second, you still blend a little of your previous direction into the new downhill direction, so your path stays coordinated rather than zig-zagging. The amount you blend in is a single number, and the two famous recipes for that number are named Fletcher-Reeves and Polak-Ribière.

Two practical worries appear that the perfect bowl never had. Because the landscape keeps changing, the careful coordination slowly drifts out of tune, so every so often you throw away the accumulated direction and just step straight downhill again — a restart. And because a blended direction might accidentally point uphill on a curved surface, you have to choose your step length carefully enough to keep heading down.

The payoff is the same one that made the original method popular: each step stores only a couple of vectors and costs one gradient, so the method scales to problems with millions of variables where richer methods cannot afford the memory.

Visual Beginner

Picture two valleys side by side. The left one is the perfect bowl of the earlier method; the right one is a banana-shaped curved valley, the kind that bends as you descend. On the bowl, the coordinated directions reach the bottom in a couple of long clean strides. On the curved valley, the same blended directions still help — the path is far straighter than plain steepest descent — but the coordination gradually slips, so once in a while the path takes a fresh straight-downhill step to reset itself.

Read the table to see how the new method differs from both of its ancestors.

feature	steepest descent	linear CG (perfect bowl)	nonlinear CG (curved valley)
direction	straight downhill	downhill blended with last direction	downhill blended with last direction
how slope is found	measured each step	read from the fixed matrix	measured each step
reaches bottom in n steps?	no	yes, exactly	only if the valley is a bowl
restarts needed?	never	never	yes, every so often
memory per step	tiny	tiny	tiny

The takeaway: nonlinear conjugate gradient borrows the coordinated-direction trick from the perfect-bowl method but measures the slope freshly each step and restarts when needed. It keeps the small memory footprint, which is why it is a workhorse for very large problems.

Worked example Beginner

Let us minimise the simple curved surface $f (x_{1}, x_{2}) = x_{1}^{2} + 4 x_{2}^{2}$ . Its lowest point is the origin. We start at the point $x_{0} = (1, 1)$ and take one nonlinear conjugate gradient step.

Step 0. The slope at a point is the pair $(2 x_{1}, 8 x_{2})$ , so at $x_{0}$ the gradient is $g_{0} = (2, 8)$ . The first direction is just straight downhill, $p_{0} = - g_{0} = (- 2, - 8)$ . We move along it by the amount that lowers the surface the most along that line; for this surface that distance works out to $α_{0} = 0.125$ , giving the new point $x_{1} = x_{0} + 0.125 p_{0} = (0.75, 0)$ .

Step 1. Measure the slope again at $x_{1}$ : the gradient is $g_{1} = (2 \cdot 0.75, 8 \cdot 0) = (1.5, 0)$ . Now we need the blend number. The Fletcher-Reeves recipe divides the new slope's squared length by the old one:

β_{1} = \frac{g _{1} \cdot g _{1}}{g _{0} \cdot g _{0}} = \frac{1. 5 ^{2} + 0 ^{2}}{2 ^{2} + 8 ^{2}} = \frac{2.25}{68} \approx 0.0331.

The next direction blends the fresh downhill direction with a little of the old direction:

p_{1} = - g_{1} + 0.0331 p_{0} = (- 1.5, 0) + 0.0331 (- 2, - 8) = (- 1.566, - 0.265) .

What this tells us: the new direction is mostly straight downhill (the $(- 1.5, 0)$ part) with a small memory of where we just came from (the tiny blend of $p_{0}$ ). That small memory is what stops the path from making the sharp wasteful turns of plain steepest descent. Each step cost only one slope measurement and stored only two short vectors.

Check your understanding Beginner

Exercise (easy, multiple choice).

What is the main reason nonlinear conjugate gradient measures the slope fresh at every step, unlike the perfect-bowl version?

Because measuring the slope is faster than reading a matrix.
Because a general curved surface has no single fixed matrix describing it, so the slope must be re-measured where you stand.
Because the gradient is more accurate than the matrix.
Because it always reaches the bottom in two steps.

Hint

The perfect-bowl method could read every slope off one matrix. A bending valley has no such matrix.

Answer

B. Feedback-correct: correct; on a general curved surface the steepness changes from place to place and there is no one matrix to read it from, so the gradient is recomputed at each new point. Feedback-wrong: speed (A) and accuracy (C) are not the reason, and the two-step finish (D) only happens on a true bowl, which is exactly the case nonlinear CG generalises away from.

Formal definition Intermediate+

Let $f : R^{n} \to R$ be continuously differentiable with gradient $g (x) = \nabla f (x)$ , and write $g_{k} = \nabla f (x_{k})$ . The nonlinear conjugate gradient iteration generalises the linear conjugate gradient method 43.07.04 from the quadratic $ϕ (x) = \frac{1}{2} x^{⊤} A x - b^{⊤} x$ (whose gradient $A x - b = - r$ supplies both the residual and the matrix $A$ ) to a general smooth $f$ , by replacing the residual $r_{k}$ with the negative gradient $- g_{k}$ and computing the step length by a line search rather than the closed-form $α_{k} = (r_{k}^{⊤} r_{k}) / (p_{k}^{⊤} A p_{k})$ . Starting from $x_{0}$ with $p_{0} = - g_{0}$ , for $k = 0, 1, 2, \dots$ ,

x_{k + 1} = x_{k} + α_{k} p_{k}, p_{k + 1} = - g_{k + 1} + β_{k + 1} p_{k},

where $α_{k}$ is chosen by a line search satisfying the strong Wolfe conditions of 44.03.01 and $β_{k + 1} \in R$ is the conjugate gradient parameter. On the quadratic $ϕ$ with exact line search every choice below reduces to the linear CG coefficient $β_{k}^{lin} = (r_{k + 1}^{⊤} r_{k + 1}) / (r_{k}^{⊤} r_{k})$ ; the methods differ only away from the quadratic.

Writing $y_{k} = g_{k + 1} - g_{k}$ , the principal parameter choices are

β_{k + 1}^{FR} = \frac{g _{k + 1}^{⊤} g _{k + 1}}{g _{k}^{⊤} g _{k}} (Fletcher-Reeves), β_{k + 1}^{PR} = \frac{g _{k + 1}^{⊤} y _{k}}{g _{k}^{⊤} g _{k}} (Polak-Ribi \overset{e}{ˋ} re),

β_{k + 1}^{HS} = \frac{g _{k + 1}^{⊤} y _{k}}{p _{k}^{⊤} y _{k}} (Hestenes-Stiefel), β_{k + 1}^{DY} = \frac{g _{k + 1}^{⊤} g _{k + 1}}{p _{k}^{⊤} y _{k}} (Dai-Yuan) .

The PR+ variant truncates the Polak-Ribière parameter at zero,

β_{k + 1}^{PR +} = max {β_{k + 1}^{PR}, 0},

which is equivalent to restarting with steepest descent ( $p_{k + 1} = - g_{k + 1}$ ) whenever the Polak-Ribière number turns negative. The new symbols $g_{k}$ , $y_{k} = g_{k + 1} - g_{k}$ , the parameters $β_{k + 1}^{FR}, β_{k + 1}^{PR}, β_{k + 1}^{HS}, β_{k + 1}^{DY}$ , and the direction recurrence are recorded in _meta/NOTATION.md.

Restarts. Because the conjugacy relations that hold exactly on a quadratic only hold approximately on a general $f$ , the accumulated direction degrades and is periodically reset. A restart sets $p_{k + 1} = - g_{k + 1}$ (equivalently $β_{k + 1} = 0$ ). Two standard triggers are a fixed schedule — restart every $n$ steps, so the method recovers the finite-termination structure of linear CG on each quadratic patch — and the Powell restart test, which restarts whenever consecutive gradients lose orthogonality,

g_{k + 1}^{⊤} g_{k} \geq 0.2 ∥ g_{k + 1} ∥^{2} .

Counterexamples to common slips Intermediate+

The four $β_{k}$ formulas are not interchangeable off the quadratic. They agree on a strictly convex quadratic with exact line search, but on a general $f$ they generate genuinely different iterates with different convergence behaviour: Fletcher-Reeves has the cleanest convergence proof, Polak-Ribière is usually faster in practice, and the two can diverge dramatically when the line search is inexact.
A descent direction is not automatic. For linear CG with exact line search $p_{k + 1}$ is always a descent direction; for nonlinear CG it can fail. Fletcher-Reeves needs the strong Wolfe conditions with $c_{2} < \frac{1}{2}$ to guarantee $g_{k + 1}^{⊤} p_{k + 1} < 0$ ; Polak-Ribière can produce an ascent direction even under strong Wolfe, which is one motivation for the PR+ truncation.
Polak-Ribière is not globally convergent in general. Powell exhibited a smooth function on which PR with exact line search cycles among three points without converging. The cure is the truncation PR+ $= max {β^{PR}, 0}$ , which is provably globally convergent. Fletcher-Reeves never cycles this way but can stall by taking many tiny steps.
Restarting is not a failure mode but part of the method. Omitting restarts on a strongly nonquadratic $f$ lets stale curvature information accumulate in $p_{k}$ ; the periodic reset to $- g_{k}$ is what keeps the method robust and is essential to the $n$ -step quadratic-termination interpretation.

Key theorem with proof Intermediate+

The signature result is that on a general smooth $f$ the Fletcher-Reeves direction stays a descent direction when the step is chosen by a sufficiently strict strong-Wolfe line search — the property that linear conjugate gradient got for free from exact line minimisation, and the property without which no global-convergence theory can even begin.

Theorem (Al-Baali descent lemma for Fletcher-Reeves). Let $f \in C^{1}$ with $g_{k} = \nabla f (x_{k}) \neq = 0$ for all $k$ , run Fletcher-Reeves from $p_{0} = - g_{0}$ with each $α_{k}$ satisfying the strong Wolfe conditions $∣ g_{k + 1}^{⊤} p_{k} ∣ \leq - c_{2} g_{k}^{⊤} p_{k}$ for a fixed $c_{2} \in (0, \frac{1}{2})$ . Then every direction is a descent direction; precisely,

- j = 0 \sum k c_{2}^{j} \leq \frac{g _{k}^{⊤} p _{k}}{∥ g _{k} ∥ ^{2}} \leq - 2 + j = 0 \sum k c_{2}^{j},

and since $\sum_{j \geq 0} c_{2}^{j} = 1/ (1 - c_{2}) < 2$ for $c_{2} < \frac{1}{2}$ , the upper bound is strictly negative, giving $g_{k}^{⊤} p_{k} < 0$ ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Proof. Induct on $k$ . For $k = 0$ , $p_{0} = - g_{0}$ gives $g_{0}^{⊤} p_{0} /∥ g_{0} ∥^{2} = - 1$ , and the bounds read $- 1 \leq - 1 \leq - 2 + 1 = - 1$ , so the base case holds with equality. Assume the bounds hold at index $k$ . The Fletcher-Reeves recurrence is $p_{k + 1} = - g_{k + 1} + β_{k + 1}^{FR} p_{k}$ with $β_{k + 1}^{FR} = ∥ g_{k + 1} ∥^{2} /∥ g_{k} ∥^{2}$ . Dividing the identity $g_{k + 1}^{⊤} p_{k + 1} = - ∥ g_{k + 1} ∥^{2} + β_{k + 1}^{FR} g_{k + 1}^{⊤} p_{k}$ by $∥ g_{k + 1} ∥^{2}$ ,

\frac{g _{k + 1}^{⊤} p _{k + 1}}{∥ g _{k + 1} ∥ ^{2}} = - 1 + β_{k + 1}^{FR} \frac{g _{k + 1}^{⊤} p _{k}}{∥ g _{k + 1} ∥ ^{2}} = - 1 + \frac{g _{k + 1}^{⊤} p _{k}}{∥ g _{k} ∥ ^{2}},

using $β_{k + 1}^{FR} = ∥ g_{k + 1} ∥^{2} /∥ g_{k} ∥^{2}$ to cancel the $∥ g_{k + 1} ∥^{2}$ .

The strong Wolfe curvature bound $∣ g_{k + 1}^{⊤} p_{k} ∣ \leq - c_{2} g_{k}^{⊤} p_{k}$ gives $c_{2} g_{k}^{⊤} p_{k} \leq g_{k + 1}^{⊤} p_{k} \leq - c_{2} g_{k}^{⊤} p_{k}$ , so dividing by $∥ g_{k} ∥^{2} > 0$ ,

- 1 + c_{2} \frac{g _{k}^{⊤} p _{k}}{∥ g _{k} ∥ ^{2}} \leq \frac{g _{k + 1}^{⊤} p _{k + 1}}{∥ g _{k + 1} ∥ ^{2}} \leq - 1 - c_{2} \frac{g _{k}^{⊤} p _{k}}{∥ g _{k} ∥ ^{2}} .

Insert the inductive bounds $- \sum_{j = 0}^{k} c_{2}^{j} \leq g_{k}^{⊤} p_{k} /∥ g_{k} ∥^{2} \leq - 2 + \sum_{j = 0}^{k} c_{2}^{j}$ . For the upper bound, $g_{k}^{⊤} p_{k} /∥ g_{k} ∥^{2} \geq - \sum_{j = 0}^{k} c_{2}^{j}$ gives $- c_{2} g_{k}^{⊤} p_{k} /∥ g_{k} ∥^{2} \leq c_{2} \sum_{j = 0}^{k} c_{2}^{j} = \sum_{j = 1}^{k + 1} c_{2}^{j}$ , so

\frac{g _{k + 1}^{⊤} p _{k + 1}}{∥ g _{k + 1} ∥ ^{2}} \leq - 1 + j = 1 \sum k + 1 c_{2}^{j} = - 2 + j = 0 \sum k + 1 c_{2}^{j} .

For the lower bound, $g_{k}^{⊤} p_{k} /∥ g_{k} ∥^{2} \leq - 2 + \sum_{j = 0}^{k} c_{2}^{j} \leq 0$ (the partial sum is below $2$ ), so $c_{2} g_{k}^{⊤} p_{k} /∥ g_{k} ∥^{2} \geq - c_{2} \sum_{j = 0}^{k} c_{2}^{j} = - \sum_{j = 1}^{k + 1} c_{2}^{j} \geq - \sum_{j = 0}^{k + 1} c_{2}^{j}$ , whence $g_{k + 1}^{⊤} p_{k + 1} /∥ g_{k + 1} ∥^{2} \geq - 1 - \sum_{j = 1}^{k + 1} c_{2}^{j} \geq - \sum_{j = 0}^{k + 1} c_{2}^{j}$ . This completes the induction. Finally $\sum_{j = 0}^{k} c_{2}^{j} < \sum_{j = 0}^{\infty} c_{2}^{j} = 1/ (1 - c_{2})$ , and $c_{2} < \frac{1}{2}$ makes $1/ (1 - c_{2}) < 2$ , so the upper bound $- 2 + \sum_{j} c_{2}^{j} < 0$ : every direction descends. $□$

Bridge. This descent guarantee is the foundational reason Fletcher-Reeves can be analysed at all on nonquadratic functions, and it builds toward the global-convergence theorem of the Advanced results, where the descent bound feeds directly into the Zoutendijk summability of 44.03.01 to force $lim inf_{k} ∥ g_{k} ∥ = 0$ . The bridge is exactly the line-search theory of 44.03.01 doing the work the matrix $A$ did for free in linear CG 43.07.04: there, exact line minimisation made $p_{k}^{⊤} g_{k + 1} = 0$ and conjugacy was automatic; here the strong Wolfe curvature bound $∣ g_{k + 1}^{⊤} p_{k} ∣ \leq - c_{2} g_{k}^{⊤} p_{k}$ is the quantitative replacement that keeps the blended direction tilted downhill. The constant $c_{2} < \frac{1}{2}$ generalises the exact-line-search limit $c_{2} \to 0$ , and this is exactly why Fletcher-Reeves with a loose curvature tolerance can lose descent while a tight one preserves it. The same telescoped geometric-series bound appears again in 44.03.04, where quasi-Newton methods instead guarantee descent through positive-definiteness of the inverse-Hessian approximation rather than through a line-search inequality. Putting these together, the central insight is that nonlinear CG trades the structural conjugacy of the quadratic case for a line-search-enforced descent condition, and the entire convergence theory rests on how strictly that condition is imposed.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Show that on the strictly convex quadratic $f (x) = \frac{1}{2} x^{⊤} A x - b^{⊤} x$ with $A ≻ 0$ and exact line search (so $g_{k + 1}^{⊤} p_{k} = 0$ and the residuals are mutually orthogonal), the Fletcher-Reeves and Polak-Ribière parameters coincide.

Hint

Use $g_{k + 1}^{⊤} g_{k} = 0$ (residual orthogonality of linear CG, 43.07.04) to simplify $β^{PR} = g_{k + 1}^{⊤} (g_{k + 1} - g_{k}) /∥ g_{k} ∥^{2}$ .

Answer

With exact line search on the quadratic, the gradients $g_{k} = - r_{k}$ are the negatives of the linear CG residuals, which are mutually orthogonal: $g_{k + 1}^{⊤} g_{k} = r_{k + 1}^{⊤} r_{k} = 0$ . Then $β_{k + 1}^{PR} = g_{k + 1}^{⊤} (g_{k + 1} - g_{k}) /∥ g_{k} ∥^{2} = (∥ g_{k + 1} ∥^{2} - g_{k + 1}^{⊤} g_{k}) /∥ g_{k} ∥^{2} = ∥ g_{k + 1} ∥^{2} /∥ g_{k} ∥^{2} = β_{k + 1}^{FR}$ . Both equal the linear CG coefficient $(r_{k + 1}^{⊤} r_{k + 1}) / (r_{k}^{⊤} r_{k})$ , so nonlinear CG with either formula reproduces linear CG exactly on a quadratic. The methods differ only where the orthogonality $g_{k + 1}^{⊤} g_{k} = 0$ fails, i.e. on a nonquadratic $f$ or with an inexact line search.

Exercise 4 (medium, symbolic).

Show that with an exact line search ( $g_{k + 1}^{⊤} p_{k} = 0$ ), the Hestenes-Stiefel and Polak-Ribière parameters coincide, and identify the common denominator.

Hint

Expand the HS denominator $p_{k}^{⊤} y_{k} = p_{k}^{⊤} (g_{k + 1} - g_{k})$ using $g_{k + 1}^{⊤} p_{k} = 0$ and $p_{k} = - g_{k} + β_{k} p_{k - 1}$ with $g_{k}^{⊤} p_{k - 1} = 0$ .

Answer

The HS parameter is $β_{k + 1}^{HS} = g_{k + 1}^{⊤} y_{k} / (p_{k}^{⊤} y_{k})$ with $y_{k} = g_{k + 1} - g_{k}$ . Expand the denominator: $p_{k}^{⊤} y_{k} = p_{k}^{⊤} g_{k + 1} - p_{k}^{⊤} g_{k} = 0 - p_{k}^{⊤} g_{k}$ using exact line search $p_{k}^{⊤} g_{k + 1} = 0$ . Now $p_{k} = - g_{k} + β_{k} p_{k - 1}$ , and exact line search at the previous step gives $g_{k}^{⊤} p_{k - 1} = 0$ , so $p_{k}^{⊤} g_{k} = - ∥ g_{k} ∥^{2} + β_{k} p_{k - 1}^{⊤} g_{k} = - ∥ g_{k} ∥^{2}$ . Hence $p_{k}^{⊤} y_{k} = ∥ g_{k} ∥^{2}$ , and $β_{k + 1}^{HS} = g_{k + 1}^{⊤} y_{k} /∥ g_{k} ∥^{2} = β_{k + 1}^{PR}$ . The common denominator is $∥ g_{k} ∥^{2}$ : with exact line search HS and PR are the same method, which is why both behave similarly in practice.

Exercise 6 (medium, symbolic).

Prove that PR+ never produces an ascent direction after a restart step: show that immediately after a restart ( $p_{k} = - g_{k}$ ), with any step length, the next PR+ direction satisfies $g_{k + 1}^{⊤} p_{k + 1} \leq - ∥ g_{k + 1} ∥^{2} + ∣ β_{k + 1}^{PR +} ∣ ∣ g_{k + 1}^{⊤} p_{k} ∣$ , and that under exact line search this is $- ∥ g_{k + 1} ∥^{2} < 0$ .

Hint

Compute $g_{k + 1}^{⊤} p_{k + 1}$ from $p_{k + 1} = - g_{k + 1} + β_{k + 1}^{PR +} p_{k}$ ; under exact line search $g_{k + 1}^{⊤} p_{k} = 0$ .

Answer

From $p_{k + 1} = - g_{k + 1} + β_{k + 1}^{PR +} p_{k}$ , take the inner product with $g_{k + 1}$ : $g_{k + 1}^{⊤} p_{k + 1} = - ∥ g_{k + 1} ∥^{2} + β_{k + 1}^{PR +} g_{k + 1}^{⊤} p_{k}$ . By Cauchy-Schwarz, $∣ β_{k + 1}^{PR +} g_{k + 1}^{⊤} p_{k} ∣ \leq ∣ β_{k + 1}^{PR +} ∣ ∣ g_{k + 1}^{⊤} p_{k} ∣$ , giving the stated bound. Under exact line search $g_{k + 1}^{⊤} p_{k} = 0$ , so $g_{k + 1}^{⊤} p_{k + 1} = - ∥ g_{k + 1} ∥^{2} < 0$ whenever $g_{k + 1} \neq = 0$ : the direction descends. The truncation $β^{PR +} = max {β^{PR}, 0} \geq 0$ matters away from exact line search, where it bounds the contribution of the $p_{k}$ term and (with a strong-Wolfe search) keeps $g_{k + 1}^{⊤} p_{k + 1} < 0$ ; allowing $β^{PR} < 0$ to act unbounded is what permits ascent and cycling.

Exercise 7 (hard, symbolic).

Establish the $n$ -step quadratic-termination property: prove that nonlinear CG with exact line search, applied to a strictly convex quadratic $f (x) = \frac{1}{2} x^{⊤} A x - b^{⊤} x$ with $A ≻ 0$ and restarted with $p_{0} = - g_{0}$ , terminates at the exact minimiser in at most $n$ steps regardless of which of FR/PR/HS/DY is used.

Hint

By Exercises 3 and 4 all four parameters equal the linear CG coefficient under exact line search on a quadratic; then invoke the finite-termination theorem of linear CG 43.07.04.

Answer

On the quadratic with exact line search, the gradients are $g_{k} = A x_{k} - b = - r_{k}$ , the negatives of the linear CG residuals, which are mutually orthogonal and span the Krylov subspaces (Key theorem of 43.07.04). By Exercise 3, $β^{FR} = β^{PR} = ∥ g_{k + 1} ∥^{2} /∥ g_{k} ∥^{2}$ , and by Exercise 4, $β^{HS} = β^{PR}$ ; the same orthogonality gives $p_{k}^{⊤} y_{k} = ∥ g_{k} ∥^{2}$ , so $β^{DY} = ∥ g_{k + 1} ∥^{2} /∥ g_{k} ∥^{2}$ as well. Thus all four parameters equal the linear CG coefficient $(r_{k + 1}^{⊤} r_{k + 1}) / (r_{k}^{⊤} r_{k})$ , and the exact-line-search step $α_{k} = (g_{k}^{⊤} g_{k}) / (p_{k}^{⊤} A p_{k})$ matches the linear CG step size. The nonlinear CG iterates therefore coincide with the linear CG iterates, which reach $x_{⋆} = A^{- 1} b$ in at most $n$ steps (finite termination of linear CG, since the conjugate directions span $R^{n}$ ). Hence nonlinear CG terminates in at most $n$ steps on a quadratic — the property that justifies the every- $n$ -steps restart schedule on a general $f$ , viewing each region near the minimiser as approximately quadratic.

Exercise 8 (hard, symbolic).

Using the Al-Baali descent bound from the Key theorem, $g_{k}^{⊤} p_{k} \leq (- 2 + \frac{1}{1 - c _{2}}) ∥ g_{k} ∥^{2} =: - τ ∥ g_{k} ∥^{2}$ with $τ > 0$ for $c_{2} < \frac{1}{2}$ , sketch the global-convergence argument for Fletcher-Reeves: combine this with Zoutendijk's condition $\sum_{k} cos^{2} θ_{k} ∥ g_{k} ∥^{2} < \infty$ from 44.03.01 to obtain $lim inf_{k} ∥ g_{k} ∥ = 0$ , assuming the directions do not grow too fast relative to the gradients.

Hint

$cos θ_{k} = - g_{k}^{⊤} p_{k} / (∥ g_{k} ∥∥ p_{k} ∥) \geq τ ∥ g_{k} ∥/∥ p_{k} ∥$ , so $cos^{2} θ_{k} ∥ g_{k} ∥^{2} \geq τ^{2} ∥ g_{k} ∥^{4} /∥ p_{k} ∥^{2}$ . Argue by contradiction that $∥ g_{k} ∥ \geq γ > 0$ forces a divergent series unless $∥ p_{k} ∥^{2}$ grows fast.

Answer

The descent bound gives $- g_{k}^{⊤} p_{k} \geq τ ∥ g_{k} ∥^{2}$ , so $cos θ_{k} = (- g_{k}^{⊤} p_{k}) / (∥ g_{k} ∥∥ p_{k} ∥) \geq τ ∥ g_{k} ∥/∥ p_{k} ∥$ and $cos^{2} θ_{k} ∥ g_{k} ∥^{2} \geq τ^{2} ∥ g_{k} ∥^{4} /∥ p_{k} ∥^{2}$ . Zoutendijk's condition (valid because the Al-Baali bound makes each $p_{k}$ a descent direction and the strong Wolfe step is used) gives $\sum_{k} τ^{2} ∥ g_{k} ∥^{4} /∥ p_{k} ∥^{2} \leq \sum_{k} cos^{2} θ_{k} ∥ g_{k} ∥^{2} < \infty$ , hence $\sum_{k} ∥ g_{k} ∥^{4} /∥ p_{k} ∥^{2} < \infty$ . Suppose for contradiction $∥ g_{k} ∥ \geq γ > 0$ for all large $k$ . The FR direction recurrence and the strong Wolfe bounds give $∥ p_{k} ∥^{2} \leq c \sum_{j \leq k} ∥ g_{j} ∥^{2}$ (a standard estimate from squaring $p_{k + 1} = - g_{k + 1} + β_{k + 1}^{FR} p_{k}$ and telescoping with $β_{k + 1}^{FR} = ∥ g_{k + 1} ∥^{2} /∥ g_{k} ∥^{2}$ ), so $∥ p_{k} ∥^{2}$ grows at most linearly in $k$ when gradients are bounded, i.e. $∥ p_{k} ∥^{2} \leq C k$ . Then $∥ g_{k} ∥^{4} /∥ p_{k} ∥^{2} \geq γ^{4} / (C k)$ , and $\sum_{k} 1/ k$ diverges, contradicting summability. Therefore $lim inf_{k} ∥ g_{k} ∥ = 0$ : Fletcher-Reeves with strong Wolfe and $c_{2} < \frac{1}{2}$ is globally convergent.

Advanced results Master

The nonlinear conjugate gradient method is the iteration $p_{k + 1} = - g_{k + 1} + β_{k + 1} p_{k}$ with a strong-Wolfe step, one object parametrised by the scalar $β_{k + 1}$ , and the results below settle which choices descend, which converge globally, where Polak-Ribière fails and how PR+ repairs it, and how the whole family relates to limited-memory quasi-Newton methods.

Theorem 1 (global convergence of Fletcher-Reeves). *Let $f \in C^{1}$ be bounded below on the level set $L = {x : f (x) \leq f (x_{0})}$ with $\nabla f$ Lipschitz on an open neighbourhood of $L$ . Run Fletcher-Reeves with strong Wolfe steps and $0 < c_{1} < c_{2} < \frac{1}{2}$ . Then $lim inf_{k \to \infty} ∥ g_{k} ∥ = 0$ .* The proof rests on the Al-Baali descent lemma (Key theorem), which delivers $- g_{k}^{⊤} p_{k} \geq τ ∥ g_{k} ∥^{2}$ with $τ = 2 - 1/ (1 - c_{2}) > 0$ , together with the bound $∥ p_{k} ∥^{2} \leq \frac{2}{τ} \sum_{j = 0}^{k} ∥ g_{j} ∥^{2}$ obtained by squaring the recurrence; substituting into Zoutendijk's condition $\sum_{k} (g_{k}^{⊤} p_{k})^{2} /∥ p_{k} ∥^{2} < \infty$ of 44.03.01 and arguing by contradiction against $∥ g_{k} ∥ \geq γ > 0$ yields the conclusion. The restriction $c_{2} < \frac{1}{2}$ is essential and is the price Fletcher-Reeves pays for its clean guarantee ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Theorem 2 (Polak-Ribière can cycle; PR+ restores convergence). There is a twice-continuously-differentiable $f$ on which Polak-Ribière with exact line search generates iterates that cycle among a neighbourhood of three points with $∥ g_{k} ∥$ bounded away from zero, so PR is not globally convergent. The truncated variant PR+ $= max {β^{PR}, 0}$ with a line search enforcing sufficient descent satisfies $lim inf_{k} ∥ g_{k} ∥ = 0$ . Powell constructed the cycling example; the mechanism is that a negative $β^{PR}$ can rotate $p_{k + 1}$ toward an ascent direction, and the line search then takes a near-zero step that fails to escape. The PR+ truncation forces a steepest-descent restart whenever $β^{PR} < 0$ , which keeps the directions in a descent cone; Gilbert and Nocedal proved global convergence of PR+ under a line search that guarantees sufficient descent ^{[Hager, W. W. & Zhang, H. — A survey of nonlinear conjugate gradient methods]}.

Theorem 3 (Dai-Yuan converges under standard Wolfe). Run the Dai-Yuan method $β_{k + 1}^{DY} = ∥ g_{k + 1} ∥^{2} / (p_{k}^{⊤} y_{k})$ with steps satisfying only the (weak) Wolfe conditions and $\nabla f$ Lipschitz, $f$ bounded below. Then $p_{k + 1}$ is a descent direction whenever $p_{k}$ is and $lim inf_{k} ∥ g_{k} ∥ = 0$ . The Dai-Yuan choice is engineered so that the descent identity $g_{k + 1}^{⊤} p_{k + 1} / (g_{k + 1}^{⊤} g_{k + 1})$ telescopes cleanly: from $p_{k + 1} = - g_{k + 1} + β_{k + 1}^{DY} p_{k}$ and $β_{k + 1}^{DY} = ∥ g_{k + 1} ∥^{2} / (p_{k}^{⊤} y_{k})$ one finds $g_{k + 1}^{⊤} p_{k + 1} = ∥ g_{k + 1} ∥^{2} (g_{k}^{⊤} p_{k}) / (p_{k}^{⊤} y_{k})$ , and the weak Wolfe curvature condition makes $p_{k}^{⊤} y_{k} > 0$ , propagating the sign. Dai-Yuan thus attains global convergence under the weakest line search of the four, the complement to Fletcher-Reeves which needs the strongest ^{[Hager, W. W. & Zhang, H. — A survey of nonlinear conjugate gradient methods]}.

Theorem 4 (the $β_{k}$ family, restarts, and the L-BFGS comparison). The choices FR, PR(+), HS, DY are members of a one-parameter family of conjugate-gradient methods; all coincide on a strictly convex quadratic with exact line search and reduce nonlinear CG to linear CG 43.07.04, giving $n$ -step termination. On a general $f$ , periodic restart with $p = - g$ every $n$ steps, or the Powell test $∣ g_{k + 1}^{⊤} g_{k} ∣ \geq 0.2∥ g_{k + 1} ∥^{2}$ , recovers approximate finite-termination behaviour and clears stale curvature. The practical significance is memory: nonlinear CG stores only $O (n)$ data — the vectors $x_{k}$ , $g_{k}$ , $p_{k}$ — and costs one gradient and a handful of inner products per step, against the $O (mn)$ storage of limited-memory BFGS 44.03.04 with history length $m$ . For very large $n$ , CG (especially HS/PR+ hybrids such as CG_DESCENT) is competitive with L-BFGS at $m$ small and is preferred when even $m \approx 5$ – $20$ vectors are too expensive; L-BFGS typically wins when its modest extra memory is affordable, because its curvature model gives faster asymptotic progress than the single-direction CG blend ^{[Hager, W. W. & Zhang, H. — A survey of nonlinear conjugate gradient methods]}.

Synthesis. Nonlinear conjugate gradient is one method — the recurrence $p_{k + 1} = - g_{k + 1} + β_{k + 1} p_{k}$ with a Wolfe step — viewed under one invariant, the scalar $β_{k + 1}$ , and the foundational reason the whole family exists is that on a strictly convex quadratic with exact line search every choice collapses to the single linear CG coefficient of 43.07.04, so nonlinear CG is linear CG plus a recipe for what to do when the quadratic model breaks. This is exactly the division of labour the line-search theory of 44.03.01 enforces: the strong Wolfe condition owns descent and globalisation, while the choice of $β_{k + 1}$ owns the curvature memory, and the two are dual in the sharpest sense — Fletcher-Reeves needs the strongest line search ( $c_{2} < \frac{1}{2}$ ) to descend but converges cleanly, while Dai-Yuan needs the weakest (plain Wolfe) because its $β$ is engineered to propagate descent algebraically. The central insight is that the conjugacy which the matrix $A$ guaranteed for free in linear CG must here be manufactured step by step, and it degrades, which is why restarts are not a patch but a structural ingredient that reasserts the $n$ -step quadratic-termination property on each near-quadratic patch.

Putting these together, the Polak-Ribière story is the cautionary face of the same principle: PR's $β$ self-restarts adaptively (it shrinks toward zero when consecutive gradients are similar) and is fast in practice, yet it can cycle because nothing stops $β^{PR} < 0$ from rotating the direction uphill — and the PR+ truncation $max {β^{PR}, 0}$ is precisely the minimal restart-enforcing repair, the bridge from a fast heuristic to a convergent method. The family generalises linear CG outward and connects downward to L-BFGS 44.03.04: both are low-memory answers to the same large-scale problem, CG carrying one direction of memory and L-BFGS carrying $m$ , and the trade is memory against asymptotic rate.

Full proof set Master

Proposition 1 (quadratic reduction). On $f (x) = \frac{1}{2} x^{⊤} A x - b^{⊤} x$ , $A ≻ 0$ , with exact line search and $p_{0} = - g_{0}$ , the FR, PR, HS, and DY parameters all equal $(r_{k + 1}^{⊤} r_{k + 1}) / (r_{k}^{⊤} r_{k})$ and nonlinear CG coincides with linear CG, terminating in at most $n$ steps.

Proof. The gradients are $g_{k} = A x_{k} - b = - r_{k}$ . Exact line search gives $g_{k + 1}^{⊤} p_{k} = 0$ , and by the linear CG theory of 43.07.04 the residuals are mutually orthogonal, $g_{k + 1}^{⊤} g_{k} = 0$ . Then $β_{k + 1}^{PR} = (∥ g_{k + 1} ∥^{2} - g_{k + 1}^{⊤} g_{k}) /∥ g_{k} ∥^{2} = ∥ g_{k + 1} ∥^{2} /∥ g_{k} ∥^{2} = β_{k + 1}^{FR}$ . From $p_{k} = - g_{k} + β_{k} p_{k - 1}$ and $g_{k}^{⊤} p_{k - 1} = 0$ one gets $p_{k}^{⊤} g_{k} = - ∥ g_{k} ∥^{2}$ , so $p_{k}^{⊤} y_{k} = p_{k}^{⊤} (g_{k + 1} - g_{k}) = 0 - (- ∥ g_{k} ∥^{2}) = ∥ g_{k} ∥^{2}$ , whence $β_{k + 1}^{HS} = g_{k + 1}^{⊤} y_{k} /∥ g_{k} ∥^{2} = β_{k + 1}^{PR}$ and $β_{k + 1}^{DY} = ∥ g_{k + 1} ∥^{2} /∥ g_{k} ∥^{2} = β_{k + 1}^{FR}$ . All four equal the linear CG coefficient; the exact step $α_{k} = ∥ g_{k} ∥^{2} / (p_{k}^{⊤} A p_{k})$ matches linear CG, so the iterates coincide and inherit finite termination in at most $n$ steps. $□$

Proposition 2 (Al-Baali descent bound). Under strong Wolfe steps with $c_{2} \in (0, \frac{1}{2})$ , Fletcher-Reeves satisfies $- \sum_{j = 0}^{k} c_{2}^{j} \leq g_{k}^{⊤} p_{k} /∥ g_{k} ∥^{2} \leq - 2 + \sum_{j = 0}^{k} c_{2}^{j}$ , so $g_{k}^{⊤} p_{k} < 0$ for all $k$ .

Proof. This is the Key theorem; the induction uses the FR cancellation $g_{k + 1}^{⊤} p_{k + 1} /∥ g_{k + 1} ∥^{2} = - 1 + g_{k + 1}^{⊤} p_{k} /∥ g_{k} ∥^{2}$ together with the strong Wolfe bound $∣ g_{k + 1}^{⊤} p_{k} ∣ \leq - c_{2} g_{k}^{⊤} p_{k}$ , and $\sum_{j \geq 0} c_{2}^{j} = 1/ (1 - c_{2}) < 2$ for $c_{2} < \frac{1}{2}$ makes the upper bound strictly negative. $□$

Proposition 3 (direction-norm bound for FR). Under the hypotheses of Proposition 2, $∥ p_{k} ∥^{2} \leq \frac{2}{τ} j = 0 \sum k ∥ g_{j} ∥^{2}$ where $τ = 2 - 1/ (1 - c_{2}) > 0$ .

Proof. Square $p_{k + 1} = - g_{k + 1} + β_{k + 1}^{FR} p_{k}$ : $∥ p_{k + 1} ∥^{2} = ∥ g_{k + 1} ∥^{2} - 2 β_{k + 1}^{FR} g_{k + 1}^{⊤} p_{k} + (β_{k + 1}^{FR})^{2} ∥ p_{k} ∥^{2}$ . The strong Wolfe bound and $β_{k + 1}^{FR} = ∥ g_{k + 1} ∥^{2} /∥ g_{k} ∥^{2} > 0$ give $- 2 β_{k + 1}^{FR} g_{k + 1}^{⊤} p_{k} \leq 2 β_{k + 1}^{FR} c_{2} (- g_{k}^{⊤} p_{k})$ . Dividing the recursion by $∥ g_{k + 1} ∥^{4}$ and telescoping the resulting bound on $∥ p_{k} ∥^{2} /∥ g_{k} ∥^{4}$ , using $- g_{k}^{⊤} p_{k} \leq \sum_{j = 0}^{k} c_{2}^{j} ∥ g_{k} ∥^{2} \leq ∥ g_{k} ∥^{2} / (1 - c_{2})$ from Proposition 2 and Cauchy-Schwarz, yields $∥ p_{k + 1} ∥^{2} /∥ g_{k + 1} ∥^{4} \leq \sum_{j = 0}^{k + 1} 1/∥ g_{j} ∥^{2} \cdot κ^{'}$ for a constant absorbing $c_{2}$ ; collecting terms and using $τ \leq - g_{k}^{⊤} p_{k} /∥ g_{k} ∥^{2}$ produces the stated linear-in- $k$ growth $∥ p_{k} ∥^{2} \leq (2/ τ) \sum_{j \leq k} ∥ g_{j} ∥^{2}$ . $□$

Proposition 4 (global convergence of FR). Under the hypotheses of Theorem 1, $lim inf_{k} ∥ g_{k} ∥ = 0$ .

Proof. Proposition 2 gives $- g_{k}^{⊤} p_{k} \geq τ ∥ g_{k} ∥^{2}$ , so $cos^{2} θ_{k} ∥ g_{k} ∥^{2} = (g_{k}^{⊤} p_{k})^{2} /∥ p_{k} ∥^{2} \geq τ^{2} ∥ g_{k} ∥^{4} /∥ p_{k} ∥^{2}$ . Zoutendijk's condition of 44.03.01 (applicable because each $p_{k}$ descends and the step is strong-Wolfe) gives $\sum_{k} (g_{k}^{⊤} p_{k})^{2} /∥ p_{k} ∥^{2} < \infty$ , so $\sum_{k} ∥ g_{k} ∥^{4} /∥ p_{k} ∥^{2} < \infty$ . If $∥ g_{k} ∥ \geq γ > 0$ for all large $k$ , Proposition 3 gives $∥ p_{k} ∥^{2} \leq (2/ τ) \sum_{j \leq k} ∥ g_{j} ∥^{2} \leq (2/ τ) (k + 1) G^{2}$ for $G = sup_{k} ∥ g_{k} ∥ < \infty$ (gradients are bounded on the compact level set), so $∥ g_{k} ∥^{4} /∥ p_{k} ∥^{2} \geq γ^{4} τ / (2 G^{2} (k + 1))$ , and $\sum_{k} 1/ (k + 1)$ diverges — a contradiction. Hence $lim inf_{k} ∥ g_{k} ∥ = 0$ . $□$

Proposition 5 (Dai-Yuan descent propagation). For Dai-Yuan with weak Wolfe steps, if $g_{k}^{⊤} p_{k} < 0$ then $p_{k}^{⊤} y_{k} > 0$ and $g_{k + 1}^{⊤} p_{k + 1} = ∥ g_{k + 1} ∥^{2} (g_{k}^{⊤} p_{k}) / (p_{k}^{⊤} y_{k}) < 0$ .

Proof. The weak Wolfe curvature condition $g_{k + 1}^{⊤} p_{k} \geq c_{2} g_{k}^{⊤} p_{k}$ gives $p_{k}^{⊤} y_{k} = g_{k + 1}^{⊤} p_{k} - g_{k}^{⊤} p_{k} \geq (c_{2} - 1) g_{k}^{⊤} p_{k} = (1 - c_{2}) (- g_{k}^{⊤} p_{k}) > 0$ since $c_{2} < 1$ and $g_{k}^{⊤} p_{k} < 0$ . Now $g_{k + 1}^{⊤} p_{k + 1} = - ∥ g_{k + 1} ∥^{2} + β_{k + 1}^{DY} g_{k + 1}^{⊤} p_{k} = - ∥ g_{k + 1} ∥^{2} + \frac{∥ g _{k + 1} ∥ ^{2}}{p _{k}^{⊤} y _{k}} g_{k + 1}^{⊤} p_{k} = ∥ g_{k + 1} ∥^{2} \frac{g _{k + 1}^{⊤} p _{k} - p _{k}^{⊤} y _{k}}{p _{k}^{⊤} y _{k}} = ∥ g_{k + 1} ∥^{2} \frac{g _{k}^{⊤} p _{k}}{p _{k}^{⊤} y _{k}}$ , using $g_{k + 1}^{⊤} p_{k} - p_{k}^{⊤} y_{k} = g_{k + 1}^{⊤} p_{k} - (g_{k + 1}^{⊤} p_{k} - g_{k}^{⊤} p_{k}) = g_{k}^{⊤} p_{k}$ . Since $g_{k}^{⊤} p_{k} < 0$ and $p_{k}^{⊤} y_{k} > 0$ , this is negative. With $p_{0} = - g_{0}$ descending, induction propagates descent at every step. $□$

Proposition 6 (PR+ descent under sufficient-descent line search). If the line search enforces $g_{k + 1}^{⊤} p_{k} \geq - σ ∥ g_{k + 1} ∥∥ p_{k} ∥$ for some $σ$ tied to $c_{2}$ and $β_{k + 1}^{PR +} = max {β_{k + 1}^{PR}, 0} \geq 0$ , then there is a constant $c > 0$ , independent of $k$ , with $g_{k + 1}^{⊤} p_{k + 1} \leq - c ∥ g_{k + 1} ∥^{2}$ along iterations between restarts.

Proof. From $p_{k + 1} = - g_{k + 1} + β_{k + 1}^{PR +} p_{k}$ , $g_{k + 1}^{⊤} p_{k + 1} = - ∥ g_{k + 1} ∥^{2} + β_{k + 1}^{PR +} g_{k + 1}^{⊤} p_{k}$ . At a restart $β_{k + 1}^{PR +} = 0$ gives $g_{k + 1}^{⊤} p_{k + 1} = - ∥ g_{k + 1} ∥^{2}$ , the case $c = 1$ . Between restarts $β_{k + 1}^{PR +} \geq 0$ and the sufficient-descent line-search bound controls the cross term: $β_{k + 1}^{PR +} g_{k + 1}^{⊤} p_{k} \leq β_{k + 1}^{PR +} σ ∥ g_{k + 1} ∥∥ p_{k} ∥$ , and a bound $β_{k + 1}^{PR +} ∥ p_{k} ∥ \leq (1 - c) ∥ g_{k + 1} ∥$ — enforced by the line search (CG_DESCENT) or by the restart trigger that fires before the accumulated direction grows too large — yields $g_{k + 1}^{⊤} p_{k + 1} \leq - ∥ g_{k + 1} ∥^{2} + (1 - c) ∥ g_{k + 1} ∥^{2} = - c ∥ g_{k + 1} ∥^{2}$ . The truncation $β^{PR +} \geq 0$ is what makes the cross term controllable; an unrestricted negative $β^{PR}$ admits $g_{k + 1}^{⊤} p_{k + 1} > 0$ , the ascent that underlies Powell's cycling example. $□$

Connections Master

The conjugate gradient method 43.07.04 is the parent algorithm that this unit generalises from quadratics to arbitrary smooth objectives. On a strictly convex quadratic with exact line search, every nonlinear CG parameter (FR, PR, HS, DY) collapses to the single linear CG coefficient $(r_{k + 1}^{⊤} r_{k + 1}) / (r_{k}^{⊤} r_{k})$ , the residual $r_{k}$ becomes the negative gradient $- g_{k}$ , and the closed-form step $(r_{k}^{⊤} r_{k}) / (p_{k}^{⊤} A p_{k})$ becomes a line search; the $A$ -conjugacy that the matrix supplied for free degrades on a nonquadratic surface and must be reasserted by restarts, which is the structural reason nonlinear CG restarts where linear CG never needs to.
Line-search methods: Wolfe conditions and global convergence 44.03.01 supplies the machinery without which nonlinear CG has no theory: the strong Wolfe conditions are what make the Fletcher-Reeves direction a descent direction (the Al-Baali bound needs $c_{2} < \frac{1}{2}$ ), and Zoutendijk's summability $\sum_{k} cos^{2} θ_{k} ∥ g_{k} ∥^{2} < \infty$ is the engine of the global-convergence proofs for FR and DY here. The division of labour that unit establishes — line search owns globalisation, the direction owns the rate — is exactly what splits the FR/DY descent guarantees from the $β_{k}$ -choice that governs practical speed.
Quasi-Newton (BFGS/DFP) and limited-memory L-BFGS methods 44.03.04 are the alternative low-memory family that nonlinear CG competes with at large scale: both avoid storing a full Hessian, CG carrying a single direction of curvature memory and L-BFGS carrying $m$ secant pairs, and the same strong/weak Wolfe line search underlies both. The trade-off — CG's $O (n)$ storage against L-BFGS's $O (mn)$ and faster asymptotic convergence — is the choice a practitioner makes for a given memory budget, and the hybrid Hestenes-Stiefel / PR+ methods such as CG_DESCENT sit at the aggressive-memory-economy end of that spectrum.

Historical & philosophical context Master

The conjugate gradient method was introduced for linear systems by Hestenes and Stiefel in 1952 ^{[Hestenes, M. R. & Stiefel, E. — Methods of Conjugate Gradients (1952)]}. Its extension to general nonlinear functions is due to Roger Fletcher and Colin Reeves, whose 1964 paper Function minimization by conjugate gradients replaced the residual by the gradient and the closed-form step by a line search, producing the first nonlinear conjugate gradient method ^{[Fletcher, R. & Reeves, C. M. — Function minimization by conjugate gradients (1964)]}. The alternative parameter now bearing their names was given independently by Elijah Polak and Gérard Ribière in 1969 and by Boris Polyak in the same year; in practice Polak-Ribière converged faster, though its convergence theory proved more delicate ^{[Polak, E. & Ribière, G. — Note sur la convergence de méthodes de directions conjuguées (1969)]}.

The theoretical picture sharpened over the following decades. M. J. D. Powell exhibited in 1984 a smooth function on which Polak-Ribière with exact line search cycles without converging, showing that the faster method lacked a global guarantee; Jean-Charles Gilbert and Jorge Nocedal then proved in 1992 that the truncated variant PR+ $= max {β^{PR}, 0}$ is globally convergent under a sufficient-descent line search. Mehiddin Al-Baali had established in 1985 the descent and global-convergence property of Fletcher-Reeves under the strong Wolfe conditions with $c_{2} < \frac{1}{2}$ . Yu-Hong Dai and Yaxiang Yuan introduced in 1999 a parameter converging under the weak Wolfe conditions, completing the spectrum from the strongest to the weakest line-search requirement ^{[Dai, Y. H. & Yuan, Y. — A nonlinear conjugate gradient method (1999)]}. William Hager and Hongchao Zhang's 2006 survey and their CG_DESCENT method unified the $β_{k}$ family and supplied a line search guaranteeing sufficient descent independently of the objective ^{[Hager, W. W. & Zhang, H. — A survey of nonlinear conjugate gradient methods]}.

Bibliography Master

@article{FletcherReeves1964,
  author  = {Fletcher, Roger and Reeves, Colin M.},
  title   = {Function minimization by conjugate gradients},
  journal = {The Computer Journal},
  volume  = {7},
  number  = {2},
  year    = {1964},
  pages   = {149--154}
}

@article{PolakRibiere1969,
  author  = {Polak, Elijah and Ribi\`{e}re, G\'{e}rard},
  title   = {Note sur la convergence de m\'{e}thodes de directions conjugu\'{e}es},
  journal = {Revue Fran\c{c}aise d'Informatique et de Recherche Op\'{e}rationnelle},
  volume  = {3},
  number  = {16},
  year    = {1969},
  pages   = {35--43}
}

@article{Polyak1969,
  author  = {Polyak, Boris T.},
  title   = {The conjugate gradient method in extremal problems},
  journal = {USSR Computational Mathematics and Mathematical Physics},
  volume  = {9},
  number  = {4},
  year    = {1969},
  pages   = {94--112}
}

@article{AlBaali1985,
  author  = {Al-Baali, Mehiddin},
  title   = {Descent property and global convergence of the Fletcher-Reeves method with inexact line search},
  journal = {IMA Journal of Numerical Analysis},
  volume  = {5},
  number  = {1},
  year    = {1985},
  pages   = {121--124}
}

@article{Powell1984,
  author    = {Powell, M. J. D.},
  title     = {Nonconvex minimization calculations and the conjugate gradient method},
  booktitle = {Numerical Analysis (Dundee 1983)},
  series    = {Lecture Notes in Mathematics},
  volume    = {1066},
  publisher = {Springer},
  year      = {1984},
  pages     = {122--141}
}

@article{GilbertNocedal1992,
  author  = {Gilbert, Jean-Charles and Nocedal, Jorge},
  title   = {Global convergence properties of conjugate gradient methods for optimization},
  journal = {SIAM Journal on Optimization},
  volume  = {2},
  number  = {1},
  year    = {1992},
  pages   = {21--42}
}

@article{DaiYuan1999,
  author  = {Dai, Yu-Hong and Yuan, Yaxiang},
  title   = {A nonlinear conjugate gradient method with a strong global convergence property},
  journal = {SIAM Journal on Optimization},
  volume  = {10},
  number  = {1},
  year    = {1999},
  pages   = {177--182}
}

@article{HagerZhang2006,
  author  = {Hager, William W. and Zhang, Hongchao},
  title   = {A survey of nonlinear conjugate gradient methods},
  journal = {Pacific Journal of Optimization},
  volume  = {2},
  number  = {1},
  year    = {2006},
  pages   = {35--58}
}

@book{NocedalWright2006ncg,
  author    = {Nocedal, Jorge and Wright, Stephen J.},
  title     = {Numerical Optimization},
  edition   = {2},
  publisher = {Springer},
  year      = {2006}
}

@book{Fletcher1987,
  author    = {Fletcher, Roger},
  title     = {Practical Methods of Optimization},
  edition   = {2},
  publisher = {Wiley},
  year      = {1987}
}

Prerequisites

44.03.01
43.07.04

Tier anchors

beginner: The same downhill-and-don't-spoil-your-earlier-steps idea as linear conjugate gradient, but now the valley is not a perfect bowl, so you must re-feel the slope each step and occasionally start over — Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §5.2 (nonlinear CG, the Fletcher-Reeves and Polak-Ribière formulas in pictures); Shewchuk 1994 An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (CMU technical report) §14 (the extension of CG to general functions and the role of restarts)
intermediate: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §5.2 (the Fletcher-Reeves method, the Polak-Ribière and PR+ variants, Hestenes-Stiefel and Dai-Yuan, the strong-Wolfe line search that guarantees descent, restart strategies, and n-step quadratic termination); Fletcher 1987 Practical Methods of Optimization 2e (Wiley) §4.1 (conjugate-gradient methods for general functions and the restart question)
master: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §5.2 and the global-convergence analysis of Fletcher-Reeves under strong Wolfe (the Al-Baali descent lemma) together with the PR cycling example and the PR+ fix; Hager & Zhang 2006 A survey of nonlinear conjugate gradient methods (Pacific J. Optim. 2, 35-58) (the unified $β_{k}$ family, descent and global-convergence theory, and the CG_DESCENT line search); Dai & Yuan 1999 A nonlinear conjugate gradient method with a strong global convergence property (SIAM J. Optim. 10, 177-182)

References

Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.) · Springer Series in Operations Research and Financial Engineering (2006). Chapter 5 'Conjugate Gradient Methods', §5.2 'Nonlinear Conjugate Gradient Methods': the Fletcher-Reeves iteration $p_{k + 1} = - \nabla f_{k + 1} + β_{k + 1}^{F R} p_{k}$ with $β_{k + 1}^{F R} = \nabla f_{k + 1}^{⊤} \nabla f_{k + 1} / (\nabla f_{k}^{⊤} \nabla f_{k})$ ; the Polak-Ribière formula $β_{k + 1}^{P R} = \nabla f_{k + 1}^{⊤} (\nabla f_{k + 1} - \nabla f_{k}) / (\nabla f_{k}^{⊤} \nabla f_{k})$ and the PR+ truncation $β^{P R +} = max {β^{P R}, 0}$ ; the Hestenes-Stiefel choice $β^{H S} = \nabla f_{k + 1}^{⊤} y_{k} / (p_{k}^{⊤} y_{k})$ with $y_{k} = \nabla f_{k + 1} - \nabla f_{k}$ ; the role of the strong Wolfe conditions in guaranteeing that $p_{k + 1}$ is a descent direction for FR when $c_{2} < 1/2$ ; the restart strategy (restart with steepest descent every $n$ steps or when consecutive gradients lose orthogonality, the Powell restart test $∣\nabla f_{k + 1}^{⊤} \nabla f_{k} ∣ \geq 0.2∥\nabla f_{k + 1} ∥^{2}$ ); the n-step quadratic-termination property reducing nonlinear CG to linear CG on a strictly convex quadratic; the Zoutendijk-based global-convergence theorem for FR under strong Wolfe (Al-Baali) and the observation that PR can fail to converge (Powell's cycling example) while PR+ restores convergence; and the comparison with limited-memory BFGS for large-scale problems.
Hager, W. W. & Zhang, H. — A survey of nonlinear conjugate gradient methods · Pacific Journal of Optimization 2 (2006), 35-58: a unified treatment of the conjugate-gradient parameter $β_{k}$ collecting the Fletcher-Reeves, Polak-Ribière(-Polyak), Hestenes-Stiefel, Dai-Yuan, conjugate-descent, Liu-Storey and hybrid choices into one family; the sufficient-descent condition $\nabla f_{k}^{⊤} p_{k} \leq - c ∥\nabla f_{k} ∥^{2}$ and which $β_{k}$ formulas guarantee it under which line searches; the global-convergence theory (the Zoutendijk condition, the Fletcher-Reeves convergence under strong Wolfe with $c_{2} \leq 1/2$ , the Dai-Yuan convergence under standard Wolfe, the PR/HS convergence subtleties and the role of the $max {\cdot, 0}$ truncation); and the CG_DESCENT method and its Wolfe line search that enforces sufficient descent independently of the objective.
Fletcher, R. — Practical Methods of Optimization (2nd ed.) · Wiley (1987). §4.1 'Conjugate Gradient Methods': the derivation of the Fletcher-Reeves method as a memoryless extension of linear CG to a general smooth $f$ via successive line minimizations, the equivalence of FR and PR on a quadratic, the necessity of (near-)exact line searches or strong Wolfe conditions to retain the descent and conjugacy properties, the restart heuristics that periodically discard the accumulated direction in favour of steepest descent to recover finite-termination-like behaviour and to clear the effect of nonquadratic curvature, and the practical observation that Polak-Ribière is usually faster in practice though Fletcher-Reeves has the cleaner convergence guarantee.

Estimated time

beginner: 18m
intermediate: 46m
master: 88m