From a quadratic to a general objective
For a symmetric positive-definite quadratic, conjugate gradient (CG) uses the previous direction to avoid undoing progress along it. Its short recurrence and finite termination depend on fixed curvature and exact arithmetic. Can we reuse the economical recurrence when the objective is not quadratic? Nonlinear conjugate gradient does precisely that, but the word conjugate is a reminder of its origin, not a promise that all new directions are conjugate with respect to one matrix.
Definition 7.3.1
(Fletcher–Reeves nonlinear conjugate gradient)
Let be continuously differentiable, , and choose . If , stop. Otherwise choose a positive step , set , and use
A point with is stationary, though it need not minimize a nonconvex function. The denominator of is nonzero because we stopped when . An implementation stores only a few vectors and needs gradients rather than a Hessian. Other choices of define different methods; their guarantees are not automatically FR guarantees.
The direction should satisfy . Differentiating at zero gives ; hence a strictly negative value guarantees a decrease for all sufficiently small positive steps. A negative coefficient on alone is not enough: the inherited direction can overwhelm it.
Exact line searches and the quadratic calculation
Suppose is an interior exact minimizer of the differentiable line function. Then
Thus the next FR direction is strictly descending whenever . The orthogonality is to the previous direction, not necessarily to every earlier direction on a nonlinear objective. An exact line minimizer may be expensive or may not exist on the positive ray, so this observation is not a practical line-search guarantee by itself.
For the special quadratic , with symmetric positive definite, the gradient change is , and exact steps produce the conjugacy that gives the method its name.
Theorem 7.3.2
(Conjugacy of exact Fletcher–Reeves steps on a quadratic)
Let with symmetric positive definite, and run FR with exact line searches until a gradient vanishes. Then the directions produced are mutually -conjugate, and each gradient is orthogonal to .
Proof
(Induction on the number of steps)
At the first step, and , so . Suppose the directions through are mutually -conjugate and is orthogonal to all earlier directions. Exact line search gives ; the gradient update and conjugacy give for . Since when , we also have . Thus, using ,
Consequently for the FR choice. For , the identity and the just-proved orthogonality show : both and lie in the span of . Hence as well. This closes the induction, with as its base.
Standard linear CG then terminates in at most steps on this quadratic; neither all-pairs conjugacy nor finite termination follows for an arbitrary nonlinear .
A complete two-dimensional step
Worked example 7.3.3
(Two exact FR steps on a diagonal quadratic)
Take , so , and . Then , , and exact line minimization gives
Since and , we have and . Indeed . A second exact step has and reaches . This finite termination illustrates the quadratic theorem; it is not a prediction for a general nonlinear problem.
The bound of steps is only an upper bound, as a starting point on a coordinate axis shows.
Worked example 7.3.4
(Termination in fewer than n steps)
For the same , start at . Then , and , so and . The method stops after one step, and , whose denominator would be , is never formed. The starting error lies in a single eigenvector of , so one search direction already suffices.
Inexact searches: what strong Wolfe buys
In practice one usually accepts a sufficiently good step rather than minimizing the line function exactly.
Definition 7.3.5
(Strong Wolfe conditions)
Let be a descent direction and . A step satisfies the strong Wolfe conditions if
The first inequality is Armijo sufficient decrease. The second controls the magnitude of the new directional derivative, including after it changes sign. These conditions refer to the actual accepted step; merely choosing does not establish that a search has found one.
Theorem 7.3.6
(A uniform descent bound for Fletcher–Reeves)
Assume is continuously differentiable, , and each accepted step satisfies strong Wolfe with fixed . Form FR directions above, stopping whenever a gradient vanishes. Every direction before stopping obeys
Thus each direction is a descent direction. This statement alone does not assert convergence to a minimizer.
Proof
(Induction on the normalized slope)
Define while . Initially . Taking the dot product of the FR recurrence with and dividing by gives
Put and suppose with , so is a descent direction and the strong Wolfe conditions apply to its step. The strong curvature condition gives , so the second term has absolute value at most . Hence
These bounds imply and . Since satisfies both, induction proves the result.
Proof X-ray
Control the inherited direction
The proof tracks one scalar, the normalized slope , and the danger lies entirely in the inherited term . Strong Wolfe is spent there, and only its absolute-value form helps: ordinary Wolfe curvature bounds from below, but a large positive value could push above zero. The induction hypothesis has to carry two facts: a bound , because the curvature estimate is proportional to , and descent, , because the Wolfe conditions are only defined for a descent direction. The key move is choosing as the fixed point of , so the lower end of the interval reproduces itself. The hypothesis is spent at the upper end, where is equivalent to , that is . Nothing in the argument uses the Armijo inequality; that condition matters for convergence, not for this sign estimate.
This is a useful distinction: descent is a property of each direction, whereas convergence also depends on step lengths, smoothness, the level set and other hypotheses. Even an algorithm with descent directions can approach a non-minimizing stationary point on a nonconvex objective.
Worked example 7.3.7
(A strong Wolfe step on the same quadratic)
Return to , , , and take , . The line function has and . Try instead of the exact . Armijo holds because , and strong curvature holds because . Then , , and
Hence , inside the theorem's interval for , but not equal to the exact-search value .
The descent bound survives the inexact step. The quadratic theorem, which assumed exact searches, does not.
Counterexample mode
Inexact steps lose finite termination
A tempting claim is that FR still terminates in two steps on a two-dimensional SPD quadratic when the steps merely satisfy strong Wolfe. In the previous example , so
The directions are not conjugate. Even an exact second step, , gives , so the minimizer is not reached. Finite termination needs exact line searches (and exact arithmetic) at every step, not just the last.
Misconceptions and practical decisions
Common mistake
(Using an exact-search identity after a Wolfe step)
After an exact search, and therefore . A Wolfe step only bounds ; it generally does not make it zero, as the value above shows. Likewise, the finite-termination theorem requires a fixed SPD quadratic and exact arithmetic. Roundoff, inexact searches and variable Hessians can destroy its orthogonality identities.
Common mistake
(A small gradient does not certify a minimum)
For , the gradient at is zero, yet zero is a strict local maximum. A stopping rule based on a small gradient reports approximate stationarity; it cannot by itself certify local or global minimality.
A restart sets instead of carrying the old direction forward. It restores descent whenever , but it also discards the accumulated direction information. For FR with the theorem's assumptions a restart is not needed to establish descent; practical restart rules and numerical stopping tolerances require separate choices. Always check a reported answer by evaluating the objective and gradient, and use convexity or an appropriate second-order argument if an optimality certificate is needed.
Exercises
Exercise 7.3.8
(For the first worked example, verify and directly. Why does the latter use rather than the ordinary dot product?)
Foundation
Solution(3)
- 1
Check orthogonality to the previous direction
.
- 2
Check conjugacy
, so .
- 3
Explain the role of
Quadratic curvature is measured by the bilinear form ; Euclidean orthogonality is a different condition. Here .
Exercise 7.3.9
(Suppose an FR direction has and the accepted step satisfies strong Wolfe with . Bound , assuming .)
Core
Solution(3)
- 1
Write the normalized recurrence
, with .
- 2
Bound the inherited term
Key step
.
Because: Strong curvature gives .
- 3
Conclude
, strictly negative. This local calculation does not require that the stated ratio itself arose from earlier FR iterations.
Exercise 7.3.10
(Let , and . Is a descent direction? What does restarting do?)
Foundation
Solution(2)
- 1
Compute the proposed direction
, and its dot product with is , so it is an ascent direction.
- 2
Restart
Restarting gives with dot product , a descent direction.
Exercise 7.3.11
(At an interior exact line minimizer, prove for any finite scalar , not just FR. State why this does not prove convergence.)
CoreProof
Solution(3)
- 1
Use the first-order condition on the line
.
Because: The line function is differentiable and is an interior minimizer.
- 2
Dot the recurrence with
.
- 3
Limit of the conclusion
∎Directional descent alone gives no bound on total progress or on the nature of a limiting stationary point.