Motivation
A quadratic with positive definite Hessian has a unique minimizer, but a direct linear solve can be costly when the dimension is large. Conjugate gradient builds directions that do not undo the progress made along earlier directions. Its recurrence uses only matrix-vector products and a few stored vectors, making it particularly useful when a matrix is large and sparse. Its elegant finite-step theorem is an exact-arithmetic theorem; it should not be mistaken for a promise that floating-point implementations always stop in precisely that many steps.
For a nonlinear objective, the Hessian changes with position and a fixed quadratic model is no longer exact. Quasi-Newton methods collect gradient changes to approximate curvature. We derive the BFGS formula from its secant and positivity requirements, then separate a conditional global convergence argument from a local superlinear criterion. The distinction matters: the update formula alone does not prove that every line search, initialization, and nonlinear problem converges.
Definitions
Definition 7.1.1
(Conjugate-gradient recurrence and Krylov spaces)
Let be symmetric positive definite (SPD) and . Write and use the recurrence
and, if ,
If or a later gradient becomes zero, stop: the current iterate is the unique minimizer. Otherwise the SPD property makes all displayed denominators positive. The residual in the linear system is . The Krylov space generated by is .
Definition 7.1.2
(Secant equation)
For a nonlinear function, define and . A Hessian approximation satisfies the secant equation if . Its inverse then satisfies . One pair determines only the action on one vector, so a matrix update must specify how the remaining curvature information is chosen.
Theorem/Proposition
Theorem 7.1.3
(Conjugate gradient in exact arithmetic)
For SPD , the recurrence above either stops earlier at the unique minimizer or produces mutually orthogonal nonzero gradients and mutually -conjugate directions. After at most steps it reaches . Before termination, minimizes over .
Theorem 7.1.4
(BFGS secant and positive definiteness)
If is SPD and , then
is SPD and satisfies . Its inverse is
The curvature condition is necessary to have any SPD matrix satisfying , since it implies . It is not an incidental denominator check.
Proof sketch or proof idea
Deriving the conjugate-gradient recurrence
Proof
(Induction on orthogonality and conjugacy)
Assume inductively that the current gradient is orthogonal to all earlier directions and gradients, and that the directions are mutually -conjugate. Since , orthogonality gives . Thus the displayed is the exact minimizer of , and . For , conjugacy gives . As the previous gradients lie in the span of previous directions, is orthogonal to them as well.
To obtain , choose its coefficient so that . From , gradient orthogonality and give exactly . For , lies in the span of previous gradients, so ; the inductive conjugacy then gives . This completes the induction.
Nonzero -conjugate directions are linearly independent, since taking the -inner product of a linear relation with any one direction isolates its coefficient. There cannot be more than of them. Hence the algorithm must terminate within steps. Moreover, the recurrence puts in ; before termination the first independent directions span . The new gradient is orthogonal to their span, so the first-order condition for the SPD quadratic proves that uniquely minimizes over .
Proof X-ray
What the induction maintains
The induction carries two invariants at once: the new gradient is orthogonal to all previous directions, and the directions are mutually -conjugate. Each feeds the other. Exact line search gives , and conjugacy transports this to every earlier through . Conversely, gradient orthogonality is what makes a short recurrence enough: because , the new direction is automatically conjugate to every with , so only the single coefficient has to be chosen. Positive definiteness is used for the positive denominators and, at the end, twice more: conjugate directions are linearly independent, which bounds the number of steps by , and the first-order condition becomes minimization over . Inexact line searches and roundoff break the invariants, which is why the theorem is stated in exact arithmetic.
Why BFGS has this rank-two form
Proof
(Remove the old action on , then add the secant term)
Start with and subtract , which removes its action on . Add , which maps to . The result is symmetric and satisfies the secant equation. For any ,
Cauchy–Schwarz in the -inner product makes the first two terms nonnegative, with equality only when is a multiple of . For a nonzero such multiple, the last term is positive because . Thus is SPD. Substitute into the product and use to verify the displayed inverse formula. This derivation motivates one particular symmetric rank-two update; the secant equation alone does not uniquely determine it.
Proof X-ray
Where the curvature condition carries the definiteness
Symmetry and the secant equation are pure algebra: the subtracted term sends to , and the added term sends to . Definiteness is the real work. The first two terms of form the Cauchy–Schwarz defect in the -inner product, which needs SPD and vanishes only on the line through . The curvature condition makes the third term nonnegative everywhere, and on that line it is decisive: for the whole form equals . So a positive defect handles every direction except , and handles itself; the counterexample below shows what happens when it fails.
If is a descent direction and with , weak Wolfe gives
Thus weak Wolfe supplies the curvature condition, even when the underlying objective is not convex. A step satisfying only Armijo does not in general supply it.
A conditional global guarantee
Proposition 7.1.5
(A conditional global guarantee for quasi-Newton directions)
Suppose is bounded below with -Lipschitz gradient, every step along satisfies the weak Wolfe conditions, and the inverse approximations obey uniform spectral bounds for fixed . Then . If is also -strongly convex with minimizer , then .
Proof
(A uniform angle bound)
At a nonstationary point, , so is a descent direction, and gives
The Wolfe angle theorem therefore gives . Under strong convexity the gradient is strongly monotone; in particular , so .
The uniform spectral bounds are explicit extra assumptions: the BFGS update and positivity alone do not establish them. Consequently this argument must not be quoted as an unconditional global convergence theorem for BFGS.
A local superlinear criterion
Proposition 7.1.6
(A local superlinear criterion)
Suppose , , the Hessian is continuous at , and full steps are eventually taken with uniformly bounded. Let . If
then convergence is superlinear: .
Proof
(Expand the gradient at the limit)
Since and the Hessian is continuous at , . Hence . The criterion and the uniform bound on make the right side .
This is a sufficient criterion, not a proof that an arbitrary BFGS sequence satisfies it. Stronger BFGS superlinear theorems require additional assumptions and their own proof.
Krylov minimization and an error bound
The Krylov interpretation supplies a quantitative comparison with any polynomial, not only finite termination. Since , the error can be written as for a polynomial of degree at most with . Conversely, every such polynomial gives a point in . The CG iterate minimizes the quadratic gap on that affine space, and
Diagonalizing then yields for every admissible polynomial . For a simple explicit choice, let , , , and take . The absolute value of the factor is at most throughout , so
This bound follows from comparison with fixed-step gradient descent and need not be the sharp CG bound; more refined polynomial choices improve it. It remains meaningful before exact termination and helps explain the influence of condition number. When , all eigenvalues are equal and CG terminates in one step, consistent with a zero factor.
Testing and safeguarding curvature
Counterexample mode
Without positive curvature the update leaves the SPD cone
A tempting claim is that the BFGS update of an SPD matrix is always SPD. Take , and : then , so . With the SPD scalar the formula gives , which is negative. No positive definite secant matrix can exist for this pair, since it would force . The repair is the hypothesis , which a weak Wolfe step supplies. An implementation can skip or modify an update when curvature is inadequate, but its precise safeguard changes the algorithm and must be stated before a convergence claim is transferred to it.
The first BFGS matrix also matters: the preservation proof begins with an SPD . Starting with an indefinite matrix does not satisfy the theorem's hypothesis. Conversely, repeatedly preserving positive definiteness only ensures that each nonzero-gradient direction is descent; eigenvalues could still approach zero or infinity. The conditional global result above explicitly assumes uniform spectral bounds to control the angle.
Gradient orthogonality is an exact-arithmetic invariant
The CG induction gives more than a way to compute coefficients. At step , is orthogonal to every direction already searched. Thus no vector in their span gives a nonzero first-order change at the current point. Since the Hessian is positive definite, this first-order statement is enough for the minimizer on the affine Krylov space, not merely a stationary point there. The moment the new residual becomes zero, and no further recurrence is required.
For a scalar multiple of the identity, with , this can be checked directly. The first direction is and its exact step is ; consequently . For a general SPD matrix, different eigencomponents have different curvatures, so one scalar step generally cannot eliminate them all. The recurrence builds new directions adapted to those remaining components. Repeated eigenvalues can make the relevant Krylov space smaller than the ambient dimension, allowing earlier exact termination.
In floating-point arithmetic, the computed residual recurrence and the true residual can drift apart. Likewise, roundoff perturbs the orthogonality used by the finite termination proof. Checking the true residual occasionally is a way to assess the actual linear-system error, but the choice of a recomputation or restart rule belongs to an implementation; this mathematical proof does not specify one. A small residual implies for SPD , so interpreting a residual also depends on the scale of the smallest eigenvalue.
The quadratic error polynomial has constant term one because the initial error cannot be altered by a zero-degree correction in the Krylov space. If a polynomial with that constant term vanishes at every distinct eigenvalue of , its action annihilates every eigencomponent of the error. This gives a second explanation for early termination when there are few distinct eigenvalues. It is an exact-arithmetic statement and does not eliminate the residual-checking issue in floating-point calculations.
Worked examples
Worked example 7.1.7
(Two conjugate-gradient steps)
Take , and . Then , and . Hence and . The coefficient is , so . The next step length is and . Directly .
Worked example 7.1.8
(A one-dimensional BFGS update)
With scalar , and , the curvature product is eight. The update gives , and . Its inverse is . In one dimension the secant equation already fixes the entire updated matrix; in higher dimensions it does not.
Worked example 7.1.9
(Why an indefinite Newton matrix is dangerous)
At for , the Hessian is and the Newton direction is . The gradient is , so : the direction is ascent. An SPD approximation would make descending instead. The example is unbounded below and therefore does not satisfy the global theorem's hypotheses; it isolates the direction failure.
Common mistakes
Three errors recur with these methods.
Common mistake
(Conjugacy is not orthogonality)
The directions satisfy , not . In the first worked example, and have , while . It is the gradients that are mutually orthogonal.
Common mistake
(Transferring the finite-termination theorem)
The -step theorem concerns an SPD quadratic in exact arithmetic. Roundoff destroys exact orthogonality, and nonlinear conjugate-gradient variants do not inherit the finite-termination proof automatically. The formulas also stop when the gradient vanishes; dividing by a zero norm is not another iteration.
Common mistake
(Reading conditional BFGS results as unconditional)
Positive definiteness is preserved only when ; a secant equation alone does not guarantee it. The global result assumes uniform spectral bounds, and the superlinear criterion is a sufficient condition. Neither is an unconditional guarantee for every BFGS implementation.
Summary
The CG recurrence enforces exact line minimization and conjugacy without storing a full basis. On an SPD quadratic it reaches the solution in at most the dimension in exact arithmetic. BFGS combines a symmetric secant update with curvature positivity. Wolfe steps yield positive curvature, and additional uniform spectral bounds give a global stationarity guarantee; a separate local approximation condition gives superlinear convergence.
Exercises
Quick check
(For and , verify the first CG step and .)
Use .
Solution · Answer
, , and , so . Thus and .
Quick check
(Show that for the Hessian BFGS formula and explain why is necessary for an SPD solution.)
Apply to term by term.
Solution · Answer
The first two terms applied to cancel, while . If an SPD satisfies the secant equation, for nonzero .
Quick check
(If is SPD with eigenvalues in , bound the angle factor for at any nonzero .)
Bound below and above.
Solution · Answer
and , so the angle factor is at least . This is a simple sufficient bound, not necessarily the sharp one.
Quick check
(Suppose exactly in the local superlinear criterion, and its inverse is bounded. What does the criterion conclude, assuming the stated convergence and full-step hypotheses?)
Look at the numerator of the criterion.
Solution
The numerator in the criterion is identically zero. Its other assumptions therefore imply : convergence is superlinear. This conclusion does not establish convergence from an arbitrary starting point.