Learning curvature from a step
Newton's direction solves , where . When the Hessian is expensive, a quasi-Newton method instead maintains a symmetric approximation to its inverse and takes . If is positive definite and , this is a descent direction. The question is how to improve using gradients already computed.
Write and . For a quadratic with Hessian , , so the exact inverse satisfies . The update asks the new approximation to reproduce this observed action, even for a nonquadratic objective.
Definition 7.4.1
(Secant equation and DFP update)
Let and . A matrix satisfies the secant equation if . The pair satisfies the curvature condition if . For symmetric positive definite and such a pair, the Davidon–Fletcher–Powell (DFP) update is
The secant equation does not determine an entire matrix: one observed direction cannot reveal all curvature. The curvature condition makes and nonzero and both denominators positive. It is a condition on the pair actually used, not a consequence of positive definiteness of alone.
Theorem 7.4.2
(Secant equation and positive definiteness)
Let be symmetric positive definite and . Then the DFP matrix (1) is symmetric positive definite and satisfies .
Proof
(Substitution and a weighted Cauchy–Schwarz bound)
Each of the three terms in (1) is symmetric, so is symmetric. Multiplying (1) by gives
For any nonzero ,
Because is positive definite, is an inner product, and Cauchy–Schwarz gives , with equality exactly when and are parallel. Hence the bracket is nonnegative, and it is strictly positive when is not a multiple of ; in that case since the last term is nonnegative. If instead with , the bracket vanishes and the last term equals . The two cases exhaust all nonzero , so is positive definite.
Proof X-ray
Why the subtraction does not destroy positivity
The proof splits the nonzero vectors into two cases, and each hypothesis does its own work. Positive definiteness of is spent on the bracket: it makes an inner product, so Cauchy–Schwarz holds with strict inequality off the line through . On that line the subtracted term removes everything contributed, which is its purpose: must forget the old response . The only thing left there is the added term, and the curvature condition is spent on it. Taking shows that the condition is also necessary, since ; if , the direction itself certifies that is not positive definite. The argument closes because the two cases are exhaustive, not because any one term dominates.
The update removes the old response in the measured direction and replaces it with . It need not preserve every earlier secant equation, and the proof establishes neither convergence nor accuracy of the full matrix.
Common mistake
(Using the inverse update on a Hessian approximation)
Formula (1) updates an approximation of the inverse Hessian and enforces . Applying the same formula to an approximation of the Hessian itself enforces , which is the wrong secant equation; a Hessian approximation must satisfy . Exchanging the roles of and in (1) gives , a different update (the BFGS formula for ), not the DFP update written for .
A complete numerical step
Worked example 7.4.3
(A quadratic in two variables)
Take , and . Then and . Exact line search minimizes , whose derivative vanishes at . Hence
Here , so (1) becomes
Direct multiplication gives . Its determinant is and its first diagonal entry is positive, consistent with the theorem. It is not yet the exact inverse : the secant equation constrains its action on , not on every vector.
Continuing from shows what a second observation adds.
Worked example 7.4.4
(The second step on the same quadratic)
At the gradient is , and
Along the derivative of is , so exact line search reaches , the minimizer. The new pair is and , with , and . Then
where each entry is checked over the common denominator . In this example two exact line-search steps reach the minimizer, and is the exact inverse Hessian, so it also satisfies the first secant equation . This is a computation for this quadratic; no general finite-termination theorem is proved on this page.
Where curvature comes from
If is twice continuously differentiable along the step, the fundamental theorem of calculus gives
Thus a uniform positive curvature bound along a nonzero step guarantees . Another route is the weak Wolfe curvature condition.
Proposition 7.4.5
(The weak Wolfe condition gives a usable pair)
Let , with , and . If , then
Proof
(Subtract the two directional derivatives)
Since and ,
where the inequality is the curvature condition and the last equality uses . All three factors are positive.
This calculation assumes a step satisfying the condition exists and is accepted; it does not prove a line search terminates.
Worked example 7.4.6
(One dimension: the update forgets the old value)
In one dimension, (1) reads , whatever positive was used. Take , so , with , , and trial step . Then and . The curvature condition with holds, since . Now , and , above the proposition's bound . Hence , the reciprocal of the average slope of over . It is not : the secant pair records an average of curvature along the step, not the curvature at the new point.
Counterexample mode
A secant pair can have the wrong sign
For , take and ; the step decreases from to . Since , we get , , and . In one dimension the secant equation forces , so no positive definite update can satisfy it. Descent alone does not supply curvature: a practical method must handle such a pair, for example by skipping or modifying an update, and those choices need their own analysis.
Practice with solutions
Quick check
(If , and , calculate from (1).)
Substitute into the three terms of (1).
Solution · Answer
, which is as the secant equation requires.
Quick check
(Can a symmetric positive definite satisfy when ?)
Multiply the secant equation by .
Solution · Answer
Only in the degenerate case . If , then , a contradiction; if , the secant equation forces , which gives no curvature information.
Quick check
(Let , and . What lower bound follows for ?)
Use the proposition on the weak Wolfe condition.
Solution · Answer
. An actual accepted step may give a larger value.
Quick check
(Suppose in two dimensions. Must equal the exact inverse Hessian of a quadratic generating the pair?)
Compare the two matrices in the first worked example.
Solution · Answer
No. In the first worked example both and map to , yet they differ. Additional observations and hypotheses are needed to determine the matrix.