The information in a step
Quasi-Newton methods replace a Hessian by a matrix learned from successive iterates. Given and , the secant equation asks the new Hessian approximation to reproduce the observed change in gradient along the step. This is only one directional condition. It does not determine a whole matrix, and the observations may be unreliable or indicate negative curvature. For a nonzero gradient, a positive definite inverse approximation nevertheless guarantees that is a descent direction, because . We will distinguish maintaining that property from proving that an entire optimization algorithm converges.
For symmetric positive definite (SPD) and a pair satisfying , the BFGS update is
It satisfies and remains SPD. But when , there cannot be any SPD matrix satisfying the original secant equation: multiplying that equation by would give . Damping changes the target of the secant equation, rather than making this contradiction disappear.
A curvature safeguard
Fix a threshold with . Assume and put and . Define
Use (1) with in place of . In the first case the data already satisfy the threshold and are unchanged. In the second, , so . Thus blends the observed gradient change with the current model's prediction . The threshold is relative to the model curvature ; it is not an absolute error bound on the gradient.
Theorem 7.2.1
(Damped BFGS preserves positive definiteness)
Let be SPD, , and . Construct by (2) and set
Then , , and is SPD. In the damped case the first inequality is equality.
Proof
(Compute , then test the quadratic form)
In the unchanged case . Otherwise substitution gives
The first two terms of cancel and the last gives . For any nonzero ,
Cauchy–Schwarz in the -inner product makes the first two terms nonnegative, with equality only when is a multiple of . For a nonzero multiple, because , so the last term is positive. This proves positive definiteness. It does not prove that approximates the true Hessian well, nor that the iterates converge.
Proof X-ray
What the safeguard proves
The proof has two independent parts. The first is algebra on : because is affine in , the formula for is simply the solution of , and the case split guarantees , so is a genuine blend of and . The threshold keeps above a fixed fraction of the model curvature , not merely positive. The second part is the positive-definiteness argument for undamped BFGS with replaced by ; the safeguard enters only in the equality case of Cauchy–Schwarz, where is a multiple of and makes the last term strictly positive. Neither part refers to , which is why the theorem says nothing about Hessian accuracy or convergence.
Worked example 7.2.2
(A pair requiring damping)
Take , , and . Here , and . Hence and . Direct substitution gives
Indeed . Its first diagonal entry is positive and its determinant is , confirming positive definiteness in two dimensions. The original pair had positive curvature, but it was below the chosen relative threshold; positivity alone need not prevent damping.
Counterexample mode
The original secant equation can be impossible
For , take and . Then . No positive scalar can satisfy . With and , (2) gives and . This is a positive model, but it represents a modified secant pair, not the actual negative curvature of .
Applying inverse updates with limited memory
Storing a dense matrix can be costly. Instead choose an SPD starting matrix whose product with a vector is inexpensive, and retain pairs in chronological order, each satisfying . Write and define the conceptual inverse updates
The matrix need not be formed. To compute , perform this two-loop recursion:
- Set . For , store and replace by .
- Set . For , compute and replace by .
- Return ; a search direction is .
The recursion is justified by unwinding the factorized form of (3).
Proposition 7.2.3
(The two-loop recursion applies the inverse updates)
Let the retained pairs satisfy . In exact arithmetic the two-loop recursion returns , with defined by (3), without forming any matrix.
Proof
(Why the loop order matters)
Put . Then (3) reads . To apply the newest update to , first apply to it; the resulting vector is the input to the preceding inverse update. Repeating this gives the backward loop, since . On the way back, equals , which is precisely the forward loop. Thus the returned vector equals in exact arithmetic. With , both loops are empty and the result is .
Each update in (3) preserves SPD: for nonzero , the quadratic form is . If it vanished, both and would hold; the latter makes , a contradiction. Thus the direction is strictly descending for nonzero . The storage is for the pairs and temporary vectors, and the arithmetic is plus the cost of applying . A common choice is a positive scalar times the identity. At the next iteration one may discard the oldest pair and reconstruct the conceptual matrix from the retained pairs and a specified new base; this is not generally the same matrix as full BFGS with all past updates.
Worked example 7.2.4
(One pair, two loops)
Take , , and . Then , , and the backward loop gives . With , we have and the forward loop returns . Directly, (3) gives , and its product with is the same vector. Thus .
Worked example 7.2.5
(Two pairs recover a diagonal Newton step)
Take and the pairs and , which are exactly the gradient changes of , and let . Then and . The backward loop starts with the newest pair: gives , and then gives . Hence . The forward loop gives and , then and . This equals , the exact Newton step for ; indeed (3) gives and . Because after the backward loop, the starting matrix has no influence on this particular result.
Common mistake
(Storing the raw pair after damping)
A damped update satisfies , not . If a limited-memory history stores instead of , it does not reproduce the damped matrix; and a raw pair with makes negative or undefined, so the SPD argument for (3) no longer applies. In the negative-curvature example above, the pair to store is , not .
Even for positive pairs, finite precision and very small denominators motivate explicit numerical safeguards; the algebra above is exact arithmetic and does not specify their tolerances. A descent direction alone does not establish global convergence: line-search conditions, objective assumptions and control of direction quality are separate issues.
Exercises and solutions
Quick check
(Let , , and . Find .)
Compare with .
Solution · Answer
and , so and .
Quick check
(In one dimension take , , and . Calculate , and .)
Here .
Solution · Answer
, , so . Then and the one-dimensional secant equation gives . This differs from the original target .
Quick check
(With , , and , calculate the returned vector.)
There is a single pair, so each loop has one step.
Solution · Answer
, , so . Then , , and the final vector is . Equivalently the updated inverse is .
Quick check
(Why does positive definiteness of each not by itself prove ?)
Think about the angle between and .
Solution · Answer
It gives when , but does not bound the angle away from or control step lengths. Those missing properties matter in descent convergence arguments; positivity alone does not supply them.