44.03.04 · optimization-control / unconstrained-optimization

Quasi-Newton Methods: BFGS, DFP, and SR1

shipped3 tiersLean: none

Anchor (Master): Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §6.1-6.4 and §3.4 (the Broyden class, SR1 and its indefiniteness handling, the Dennis-Moré characterisation of superlinear convergence, the self-correcting property of BFGS, and the global-convergence theorem for BFGS with Wolfe line search); Dennis & Schnabel 1996 Numerical Methods for Unconstrained Optimization and Nonlinear Equations (SIAM) §9; Dennis & Moré 1977 Quasi-Newton methods, motivation and theory (SIAM Review)

Intuition Beginner

Newton's method is fast because it reads the curvature of the landscape — how the slope changes — and uses it to aim each step. The catch is that reading the curvature means computing a whole table of second derivatives, the Hessian, at every point. For a problem in thousands of variables that table is enormous and expensive, and sometimes you do not even have a formula for it. Quasi-Newton methods keep almost all of Newton's speed while never computing a single second derivative.

The trick is to learn the curvature as you go. Every time you take a step, you get to see two gradients: the one where you started and the one where you landed. The way the gradient changed across that step is a free measurement of the curvature along that direction. A quasi-Newton method stores a running guess of the curvature and, after each step, nudges that guess so it agrees with the new measurement. Over a handful of steps the guess sharpens into a good stand-in for the true Hessian, and the method starts taking near-Newton steps.

Think of it like mapping a dark room by walking through it. You cannot see the walls, but each time you move and feel how the floor tilts differently, you update your mental map. You never measure the whole room at once; you refine a picture from the changes you feel step by step. The requirement that the room "curve upward" along each step — so your map stays a sensible bowl rather than a saddle — is supplied by the same line-search rule from the previous unit, which guarantees the measured curvature is positive.

Visual Beginner

Picture a one-dimensional slice again: height against position. Newton fits a parabola using the exact bend at your current point. A quasi-Newton method has no exact bend to use, so instead it draws a parabola whose slope matches the gradient you measured at both the old point and the new point. A parabola is pinned down by requiring its slope to pass through those two slope readings — that single requirement is the secant condition, and it forces the parabola's curvature to equal the average rate at which the slope changed between the two points.

method	curvature it uses	cost per step	speed near a minimum
steepest descent	none (slope only)	cheapest	slow, zig-zag
Newton	exact Hessian	expensive (build + solve)	digits double
quasi-Newton	learned from gradient changes	cheap (no second derivatives)	digits almost double

The takeaway: by matching the slope at two points instead of the exact bend at one, a quasi-Newton method estimates curvature for free from gradients it already had to compute, and refines that estimate every step.

Worked example Beginner

Take the simple bowl $f (x) = \frac{1}{2} c x^{2}$ in one variable, whose true curvature is the number $c$ . Suppose $c = 4$ but pretend we do not know it; we will recover it from two gradient readings. The gradient (slope) is $f^{'} (x) = 4 x$ .

Start at $x_{0} = 3$ . The slope there is $f^{'} (3) = 12$ . Take a step to $x_{1} = 1$ . The slope there is $f^{'} (1) = 4$ . Now form the two step quantities a quasi-Newton method records: how far we moved, $s = x_{1} - x_{0} = 1 - 3 = - 2$ , and how much the slope changed, $y = f^{'} (x_{1}) - f^{'} (x_{0}) = 4 - 12 = - 8$ .

The secant estimate of the curvature is the change in slope divided by the distance moved:

B = \frac{y}{s} = \frac{- 8}{- 2} = 4.

That is exactly the true curvature $c = 4$ . On a perfect bowl, two gradient readings pin the curvature down precisely, so the learned model becomes the true Newton model after a single step.

Check the curvature is positive the way the line-search rule guarantees: $s \cdot y = (- 2) (- 8) = 16 > 0$ . A positive product means the slope rose as we moved in the positive direction (or fell as we moved in the negative direction), the signature of a curve that bends upward — a sensible bowl to step into.

What this tells us: the pair $(s, y)$ of "distance moved" and "slope change" carries the curvature, and dividing one by the other recovers it. In many variables you cannot simply divide, so the update rules of this unit are the careful matrix version of this same one-number idea, and the positive product $s \cdot y > 0$ is what keeps the matrix a genuine bowl.

Check your understanding Beginner

Formal definition Intermediate+

Let $f : R^{n} \to R$ be twice continuously differentiable with gradient $g (x) = \nabla f (x)$ . A quasi-Newton method is a line-search method 44.03.01 $x_{k + 1} = x_{k} + α_{k} p_{k}$ whose search direction $p_{k} = - H_{k} g_{k}$ uses a symmetric positive-definite matrix $H_{k}$ approximating the inverse Hessian $\nabla^{2} f (x_{k})^{- 1}$ , equivalently $p_{k}$ solves $B_{k} p_{k} = - g_{k}$ with $B_{k} = H_{k}^{- 1} \approx \nabla^{2} f (x_{k})$ . After each step define the secant pair

s_{k} = x_{k + 1} - x_{k}, y_{k} = g_{k + 1} - g_{k} .

The defining requirement is the secant equation

B_{k + 1} s_{k} = y_{k}, equivalently H_{k + 1} y_{k} = s_{k},

which forces the updated model to reproduce the gradient change across the last step: it is the multivariable form of "average curvature equals slope-change over displacement", since by Taylor's theorem 02.05.05 $y_{k} = (\int_{0}^{1} \nabla^{2} f (x_{k} + t s_{k}) d t) s_{k}$ , so $B_{k + 1}$ matches the average Hessian along the segment. The secant equation admits a symmetric positive-definite solution only when the curvature condition

s_{k}^{⊤} y_{k} > 0

holds; this is guaranteed at every iteration by the Wolfe curvature condition of the line search 44.03.01, since $s_{k}^{⊤} y_{k} = α_{k} p_{k}^{⊤} (g_{k + 1} - g_{k}) \geq α_{k} (1 - c_{2}) (- p_{k}^{⊤} g_{k}) > 0$ .

The secant equation underdetermines $B_{k + 1}$ (it is $n$ equations on a symmetric $n \times n$ matrix), so a quasi-Newton method selects the update by a least-change principle. Writing $ρ_{k} = 1/ (y_{k}^{⊤} s_{k})$ , the two classical rank-two updates are the DFP (Davidon-Fletcher-Powell) update of the Hessian approximation

B_{k + 1}^{DFP} = (I - ρ_{k} y_{k} s_{k}^{⊤}) B_{k} (I - ρ_{k} s_{k} y_{k}^{⊤}) + ρ_{k} y_{k} y_{k}^{⊤},

and the BFGS (Broyden-Fletcher-Goldfarb-Shanno) update

B_{k + 1}^{BFGS} = B_{k} - \frac{B _{k} s _{k} s _{k}^{⊤} B _{k}}{s _{k}^{⊤} B _{k} s _{k}} + \frac{y _{k} y _{k}^{⊤}}{y _{k}^{⊤} s _{k}} .

These are dual: interchanging $B \leftrightarrow H$ and $s \leftrightarrow y$ carries one into the other. Applying the Sherman-Morrison-Woodbury formula to the rank-two updates gives the inverse-Hessian forms used in practice (no linear solve, $O (n^{2})$ per step): the BFGS inverse update is

H_{k + 1}^{BFGS} = (I - ρ_{k} s_{k} y_{k}^{⊤}) H_{k} (I - ρ_{k} y_{k} s_{k}^{⊤}) + ρ_{k} s_{k} s_{k}^{⊤},

and the DFP inverse update is $H_{k + 1}^{DFP} = H_{k} - \frac{H _{k} y _{k} y _{k}^{⊤} H _{k}}{y _{k}^{⊤} H _{k} y _{k}} + \frac{s _{k} s _{k}^{⊤}}{y _{k}^{⊤} s _{k}}$ .

The symmetric rank-one (SR1) update solves the secant equation with a single symmetric rank-one correction,

B_{k + 1}^{SR1} = B_{k} + \frac{( y _{k} - B _{k} s _{k} ) ( y _{k} - B _{k} s _{k} ) ^{⊤}}{( y _{k} - B _{k} s _{k} ) ^{⊤} s _{k}},

which exists whenever the denominator is nonzero but is not required to be positive definite; SR1 can build an indefinite approximation that tracks the true Hessian's negative curvature, making it natural inside a trust region 44.03.02 rather than a line search. A standard safeguard skips the update when $∣ (y_{k} - B_{k} s_{k})^{⊤} s_{k} ∣ < r ∥ s_{k} ∥ ∥ y_{k} - B_{k} s_{k} ∥$ for a small $r$ (say $r = 1 0^{- 8}$ ). The Broyden class interpolates the two rank-two updates,

B_{k + 1}^{ϕ} = (1 - ϕ) B_{k + 1}^{BFGS} + ϕ B_{k + 1}^{DFP}, ϕ \in R,

with $ϕ = 0$ giving BFGS, $ϕ = 1$ giving DFP, and $ϕ \in [0, 1]$ the convex (restricted) Broyden class. The new symbols $s_{k}$ , $y_{k}$ (secant pair), $B_{k}$ , $H_{k}$ (Hessian and inverse-Hessian approximations), $ρ_{k}$ , and the SR1/Broyden updates are recorded in _meta/NOTATION.md.

Counterexamples to common slips Intermediate+

"Any symmetric matrix solving the secant equation will do." The secant equation is satisfied by infinitely many symmetric matrices when $n > 1$ ; without a least-change selection the iteration can drift to an approximation unrelated to the Hessian. DFP and BFGS are the minimum-change secant updates in a weighted Frobenius norm, which is what makes them stable.
"BFGS needs $s_{k}^{⊤} y_{k} > 0$ only for efficiency." Positivity is necessary for existence of a positive-definite secant update: if $s_{k}^{⊤} y_{k} \leq 0$ no symmetric positive-definite $B_{k + 1}$ can satisfy $B_{k + 1} s_{k} = y_{k}$ , because that would give $s_{k}^{⊤} y_{k} = s_{k}^{⊤} B_{k + 1} s_{k} > 0$ . The Wolfe line search is therefore not optional flavouring but the mechanism that makes the update well posed.
"SR1 is just a cheaper BFGS." SR1 deliberately abandons positive-definiteness; its denominator can vanish or turn the correction indefinite. It is preferred precisely where indefiniteness is informative — inside a trust region that can exploit negative curvature — and is unsafe as a stand-alone line-search Hessian model without the skipping safeguard.
"Quasi-Newton converges quadratically like Newton." It does not. Because $B_{k}$ only approximates the Hessian, the rate is superlinear, not quadratic; the Dennis-Moré condition characterises exactly when this superlinear rate is achieved, and it requires the approximation to act like the true Hessian along the step directions, not everywhere.

Key theorem with proof Intermediate+

The signature structural result is that the BFGS update propagates positive-definiteness: if the current model is a genuine bowl and the measured curvature is positive, the next model is a genuine bowl too. This is what guarantees the quasi-Newton direction stays a descent direction at every iteration without any explicit safeguard, so the globalisation theory of the previous unit applies unchanged.

Theorem (hereditary positive-definiteness of BFGS). Let $B_{k} ≻ 0$ be symmetric positive definite and let the curvature condition $s_{k}^{⊤} y_{k} > 0$ hold. Then the BFGS update

B_{k + 1} = B_{k} - \frac{B _{k} s _{k} s _{k}^{⊤} B _{k}}{s _{k}^{⊤} B _{k} s _{k}} + \frac{y _{k} y _{k}^{⊤}}{y _{k}^{⊤} s _{k}}

is symmetric positive definite.

Proof. Symmetry is plain since each term is symmetric. Take any $z \neq = 0$ and evaluate the quadratic form. Write $a = B_{k}^{1/2} z$ and $b = B_{k}^{1/2} s_{k}$ , both well defined because $B_{k} ≻ 0$ has a symmetric positive-definite square root 01.01.13. Then

z^{⊤} B_{k} z = a^{⊤} a = ∥ a ∥^{2}, z^{⊤} B_{k} s_{k} = a^{⊤} b, s_{k}^{⊤} B_{k} s_{k} = b^{⊤} b = ∥ b ∥^{2},

so the middle term contributes

z^{⊤} (B_{k} - \frac{B _{k} s _{k} s _{k}^{⊤} B _{k}}{s _{k}^{⊤} B _{k} s _{k}}) z = ∥ a ∥^{2} - \frac{( a ^{⊤} b ) ^{2}}{∥ b ∥ ^{2}} .

By the Cauchy-Schwarz inequality $(a^{⊤} b)^{2} \leq ∥ a ∥^{2} ∥ b ∥^{2}$ , so this quantity is $\geq 0$ , and it equals $0$ only when $a$ and $b$ are parallel, i.e. $z = λ s_{k}$ for some scalar $λ \neq = 0$ . The last term contributes $\frac{( y _{k}^{⊤} z ) ^{2}}{y _{k}^{⊤} s _{k}} \geq 0$ because $y_{k}^{⊤} s_{k} > 0$ . Hence

z^{⊤} B_{k + 1} z = \geq 0 (∥ a ∥^{2} - \frac{( a ^{⊤} b ) ^{2}}{∥ b ∥ ^{2}}) + \geq 0 \frac{( y _{k}^{⊤} z ) ^{2}}{y _{k}^{⊤} s _{k}} \geq 0.

It remains to rule out equality. Suppose $z^{⊤} B_{k + 1} z = 0$ . Both nonnegative summands must vanish. The first vanishes only if $z = λ s_{k}$ , $λ \neq = 0$ ; substituting into the second, $y_{k}^{⊤} z = λ y_{k}^{⊤} s_{k} \neq = 0$ because $y_{k}^{⊤} s_{k} > 0$ and $λ \neq = 0$ , so the second summand is strictly positive — a contradiction. Therefore $z^{⊤} B_{k + 1} z > 0$ for all $z \neq = 0$ , and $B_{k + 1} ≻ 0$ . $□$

Bridge. This is the foundational reason BFGS needs no descent-direction safeguard: $B_{k + 1} ≻ 0$ makes $p_{k + 1} = - B_{k + 1}^{- 1} g_{k + 1}$ a descent direction automatically, so the Wolfe line search of 44.03.01 always supplies a positive $s_{k + 1}^{⊤} y_{k + 1}$ , which keeps $B_{k + 2} ≻ 0$ , and the invariant propagates for the whole run. The argument builds toward the global-convergence theorem of the Advanced results, where this hereditary positivity is exactly the hypothesis that lets the angle-bounded Zoutendijk machinery apply, and it appears again in the inverse form: the same computation on $H_{k + 1}$ shows the inverse update preserves positive-definiteness, which is what makes the $O (n^{2})$ direction computation $p_{k} = - H_{k} g_{k}$ legitimate. The central insight is that the curvature condition $s_{k}^{⊤} y_{k} > 0$ — itself a gift of the Wolfe line search — is precisely the algebraic hypothesis under which a positive-definite secant update can exist at all; this is exactly the dual of the descent property of Newton's method 44.03.03, where positive-definiteness of the exact Hessian played the same role. Putting these together, the line search owns globalisation and the secant update owns the local model, and the bridge is the curvature condition that ties the two together so the quasi-Newton direction is a descent direction at every step.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

Derive the inverse-Hessian BFGS update from the direct update using the Sherman-Morrison-Woodbury identity in the compact form: show that the BFGS update can be written $B_{k + 1} = (I - ρ y s^{⊤})^{- ⊤} [\cdot]$ is unnecessary — instead verify that the stated $H_{k + 1} = (I - ρ s y^{⊤}) H (I - ρ y s^{⊤}) + ρ s s^{⊤}$ satisfies the secant equation $H_{k + 1} y = s$ , where $ρ = 1/ (y^{⊤} s)$ .

Hint

Apply $H_{k + 1}$ to $y$ . Note $(I - ρ y s^{⊤}) y = y - ρ y (s^{⊤} y) = y - y = 0$ .

Answer

Compute $(I - ρ y s^{⊤}) y = y - ρ y (s^{⊤} y) = y - y = 0$ since $ρ (s^{⊤} y) = 1$ . Therefore the first term $(I - ρ s y^{⊤}) H (I - ρ y s^{⊤}) y = 0$ . The second term gives $ρ s s^{⊤} y = s (ρ s^{⊤} y) = s \cdot 1 = s$ . Hence $H_{k + 1} y = 0 + s = s$ , the inverse secant equation. The Sherman-Morrison-Woodbury content is that this $H_{k + 1}$ is exactly $(B_{k + 1}^{BFGS})^{- 1}$ : applying the rank-two inverse formula to $B_{k + 1} = B_{k} - \frac{B _{k} s s ^{⊤} B _{k}}{s ^{⊤} B _{k} s} + \frac{y y ^{⊤}}{y ^{⊤} s}$ produces precisely the displayed congruence-plus-rank-one form, so each step costs $O (n^{2})$ with no linear solve. Full credit for $H_{k + 1} y = s$ .

Exercise 6 (hard, symbolic).

Prove that on a strongly convex quadratic $f (x) = \frac{1}{2} x^{⊤} A x - b^{⊤} x$ ( $A ≻ 0$ ), every secant pair satisfies $B_{k + 1} s_{k} = y_{k} = A s_{k}$ , so any secant update with $B_{0} = A$ gives $B_{k} = A$ for all $k$ ; hence the quasi-Newton step equals the Newton step from the first iteration.

Hint

For a quadratic, $g (x) = A x - b$ , so $y_{k} = g_{k + 1} - g_{k} = A (x_{k + 1} - x_{k}) = A s_{k}$ .

Answer

For the quadratic, $g (x) = A x - b$ , so $y_{k} = g_{k + 1} - g_{k} = A (x_{k + 1} - x_{k}) = A s_{k}$ , i.e. the exact secant pair satisfies $y_{k} = A s_{k}$ with the true Hessian $A$ . If $B_{k} = A$ then $B_{k} s_{k} = A s_{k} = y_{k}$ , so $B_{k}$ already satisfies the secant equation, and the least-change updates (BFGS, DFP, SR1) leave a matrix unchanged when it already satisfies the secant equation: each update's correction term involves $y_{k} - B_{k} s_{k} = 0$ for SR1 (zero correction), and for BFGS/DFP the rank-two terms reduce so that $B_{k + 1} = B_{k}$ when $B_{k} s_{k} = y_{k}$ and the update reproduces $A$ on the relevant subspace. By induction from $B_{0} = A$ , $B_{k} = A$ for all $k$ , and $p_{k} = - A^{- 1} g_{k}$ is the Newton step. (More is true: even from $B_{0} = I$ , BFGS on an $n$ -dimensional quadratic with exact line search builds $B_{n} = A$ and terminates in at most $n$ steps — the conjugate-direction property.) Full credit for $y_{k} = A s_{k}$ and the fixed-point argument.

Exercise 7 (hard, symbolic).

State and motivate the Dennis-Moré condition: prove that if the quasi-Newton step asymptotically agrees with the Newton step, i.e. $lim_{k \to \infty} \frac{∥ ( B _{k} - \nabla ^{2} f ( x ^{*} )) s _{k} ∥}{∥ s _{k} ∥} = 0$ , then near a strong minimiser the unit step $α_{k} = 1$ yields superlinear convergence, $∥ x_{k + 1} - x^{*} ∥/∥ x_{k} - x^{*} ∥ \to 0$ .

Hint

Write the error recursion using $g_{k} = \nabla^{2} f (x^{*}) (x_{k} - x^{*}) + o (∥ x_{k} - x^{*} ∥)$ and $B_{k} s_{k} = - g_{k}$ (the unit-step quasi-Newton equation), then compare $s_{k}$ with the Newton step.

Answer

Write $H^{*} = \nabla^{2} f (x^{*}) ≻ 0$ and $e_{k} = x_{k} - x^{*}$ . The unit quasi-Newton step solves $B_{k} s_{k} = - g_{k}$ , so $s_{k} = x_{k + 1} - x_{k}$ gives $e_{k + 1} = e_{k} + s_{k}$ . With $g_{k} = H^{*} e_{k} + o (∥ e_{k} ∥)$ (Taylor 02.05.05, $g (x^{*}) = 0$ ) and $g_{k + 1} = H^{*} e_{k + 1} + o (∥ e_{k + 1} ∥)$ ,

H^{*} e_{k + 1} = g_{k + 1} + o (∥ e_{k + 1} ∥) = (g_{k + 1} - g_{k}) + g_{k} + o = y_{k} - B_{k} s_{k} + o = (\nabla^{2} f - B_{k}) s_{k}_{avg} + o,

using $g_{k} = - B_{k} s_{k}$ and $y_{k} = \overline{H}_{k} s_{k}$ for the average Hessian $\overline{H}_{k} \to H^{*}$ . Thus $∥ H^{*} e_{k + 1} ∥ \leq ∥ (\overline{H}_{k} - B_{k}) s_{k} ∥ + o (∥ e_{k} ∥)$ , and the Dennis-Moré limit makes $∥ (\overline{H}_{k} - B_{k}) s_{k} ∥/∥ s_{k} ∥ \to 0$ . Since $∥ s_{k} ∥$ is comparable to $∥ e_{k} ∥$ near the solution (the steps and errors are of the same order once convergence sets in), dividing by $∥ e_{k} ∥$ gives $∥ e_{k + 1} ∥/∥ e_{k} ∥ \to 0$ : superlinear convergence. The condition is the exact characterisation — superlinearity holds if and only if the approximation acts like the true Hessian along the step directions, not necessarily everywhere. Full credit for the error recursion and the conclusion that the Dennis-Moré limit forces $∥ e_{k + 1} ∥/∥ e_{k} ∥ \to 0$ .

Advanced results Master

Quasi-Newton methods replace the exact Hessian solve $\nabla^{2} f p = - g$ of Newton's method 44.03.03 by a secant-updated model, and the theory below organises around three facts: the least-change variational characterisation that singles out BFGS and DFP, the Dennis-Moré characterisation that pins superlinear convergence to step-directional Hessian fidelity, and the self-correcting and global-convergence properties that make BFGS the default unconstrained optimiser.

Theorem 1 (least-change secant characterisation). Among all symmetric matrices $B$ satisfying the secant equation $B s_{k} = y_{k}$ , the DFP update is the unique minimiser of the weighted Frobenius distance $∥ W (B - B_{k}) W ∥_{F}$ with any symmetric weight $W$ satisfying $W^{2} y_{k} = s_{k}$ (e.g. $W = \overline{H}_{k}^{- 1/2}$ for the average Hessian $\overline{H}_{k} = \int_{0}^{1} \nabla^{2} f (x_{k} + t s_{k}) d t$ , which makes the derivation affine invariant). Dually, the BFGS update is the unique minimiser of the same weighted-Frobenius least-change problem on the inverse approximation $H$ , subject to $H y_{k} = s_{k}$ , with weight satisfying $W^{2} s_{k} = y_{k}$ . This variational origin explains the stability of both updates: they change the current model as little as the new curvature measurement permits, so a single inaccurate secant pair cannot corrupt the accumulated information ^{[Dennis, J. E. & Schnabel, R. B. — Numerical Methods for Unconstrained Optimization and Nonlinear Equations]}.

Theorem 2 (Dennis-Moré superlinear characterisation). Let $x_{k} \to x^{*}$ with $\nabla f (x^{*}) = 0$ , $\nabla^{2} f (x^{*}) ≻ 0$ , and $\nabla^{2} f$ Lipschitz near $x^{*}$ . If the quasi-Newton iteration takes unit steps $x_{k + 1} = x_{k} - B_{k}^{- 1} g_{k}$ with ${B_{k}}$ nonsingular, then the convergence is q-superlinear if and only if

k \to \infty lim \frac{( B _{k} - \nabla ^{2} f ( x ^{*} ) ) s _{k}}{∥ s _{k} ∥} = 0.

The condition demands only that $B_{k}$ act like the true Hessian along the step directions $s_{k}$ , not that $B_{k} \to \nabla^{2} f (x^{*})$ ; indeed BFGS and DFP need not converge to the true Hessian and yet attain the superlinear rate. This is the precise sense in which quasi-Newton trades Newton's quadratic rate for a superlinear one while shedding second derivatives ^{[Dennis, J. E. & Schnabel, R. B. — Numerical Methods for Unconstrained Optimization and Nonlinear Equations]}.

Theorem 3 (self-correcting property and global convergence of BFGS). On a twice-differentiable convex $f$ whose Hessian is bounded and Lipschitz on the level set ${f \leq f (x_{0})}$ , BFGS with a Wolfe line search 44.03.01 from any positive-definite $B_{0}$ converges to the minimiser, and the rate is superlinear. The mechanism is the self-correcting property: if at some iteration $B_{k}$ has badly distorted eigenvalues (too large or too small), the BFGS update tends to repair them over the next few iterations, because the trace and determinant identities

tr (B_{k + 1}) = tr (B_{k}) - \frac{∥ B _{k} s _{k} ∥ ^{2}}{s _{k}^{⊤} B _{k} s _{k}} + \frac{∥ y _{k} ∥ ^{2}}{y _{k}^{⊤} s _{k}}, det (B_{k + 1}) = det (B_{k}) \frac{y _{k}^{⊤} s _{k}}{s _{k}^{⊤} B _{k} s _{k}},

force a Lyapunov-type quantity (the Powell function $ψ (B) = tr (B) - ln det (B)$ ) to stay controlled, bounding the iterations on which the search direction is poorly scaled. DFP lacks an equally strong self-correcting mechanism, which is the practical reason BFGS is preferred ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Theorem 4 (SR1 and indefiniteness; trust-region convergence to the Hessian). The SR1 update, when the safeguard $∣ (y_{k} - B_{k} s_{k})^{⊤} s_{k} ∣ \geq r ∥ s_{k} ∥ ∥ y_{k} - B_{k} s_{k} ∥$ is satisfied, generates approximations that converge to the true Hessian even on nonconvex problems: under uniform linear independence of the steps and a Lipschitz Hessian, $B_{k} \to \nabla^{2} f (x^{*})$ for SR1, a stronger conclusion than BFGS gives. Because SR1 does not enforce positive-definiteness, it captures negative curvature and is therefore the natural Hessian model inside a trust-region method 44.03.02, where indefiniteness is handled by the subproblem rather than forbidden. The price is the possibility of a vanishing or sign-changing denominator, which the skipping safeguard controls; skipped updates are rare and do not impede convergence ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Theorem 5 (the Broyden class and quadratic termination). For the convex Broyden class $B_{k + 1}^{ϕ} = (1 - ϕ) B_{k + 1}^{BFGS} + ϕ B_{k + 1}^{DFP}$ with $ϕ \in [0, 1]$ , every member preserves positive-definiteness under the curvature condition and satisfies the secant equation. On a strongly convex quadratic with exact line search, every Broyden-class method generates conjugate directions with respect to the Hessian and therefore terminates at the exact minimiser in at most $n$ steps, building $B_{n} = \nabla^{2} f$ exactly. This quadratic-termination property links quasi-Newton methods to the conjugate-gradient method 44.03.06: BFGS with exact line search and $B_{0} = I$ generates the same iterates as linear conjugate gradient on a quadratic, which is the structural reason limited-memory L-BFGS 44.03.05 behaves like a preconditioned nonlinear CG on large problems ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Synthesis. Quasi-Newton optimization is one construction — approximate the Hessian by the least-change symmetric matrix satisfying the secant equation $B_{k + 1} s_{k} = y_{k}$ — and its entire theory descends from a single algebraic gift: the curvature condition $s_{k}^{⊤} y_{k} > 0$ , supplied free by the Wolfe line search 44.03.01, is exactly the hypothesis under which a positive-definite secant update exists, and this is the foundational reason BFGS needs no descent safeguard while propagating positive-definiteness hereditarily. The central insight is the division of labour inherited from the previous units: the line search owns globalisation, the secant update owns the local curvature model, and the Dennis-Moré condition reveals that superlinear speed requires the model to match the true Hessian only along the step directions — this is exactly the relaxation of Newton's requirement that the exact Hessian be used, and it is what buys the dimensionless escape from second derivatives. The BFGS and DFP updates are dual under the $B \leftrightarrow H$ , $s \leftrightarrow y$ interchange, and putting these together with the Sherman-Morrison-Woodbury inverse forms gives the $O (n^{2})$ per-step cost that is the whole practical point.

The bridge forward is explicit. The same secant idea that here approximates a symmetric Hessian generalises to the nonsymmetric Jacobian of root-finding 43.02.03, from which Broyden's method descends; the conjugate-direction property of the Broyden class is dual to the conjugate-gradient method 44.03.06, so BFGS is a memory-rich CG and L-BFGS 44.03.05 is the memory-limited bridge between them; SR1's tolerance of indefiniteness makes it the Hessian model of choice inside trust-region methods 44.03.02, where the subproblem rather than the line search absorbs negative curvature. What Newton's method 44.03.03 achieves with the exact Hessian, quasi-Newton achieves with a learned one — slightly slower, vastly cheaper — and the learned model is the central object every large-scale solver carries forward.

Full proof set Master

Proposition 1 (hereditary positive-definiteness of BFGS). If $B_{k} ≻ 0$ and $s_{k}^{⊤} y_{k} > 0$ , then $B_{k + 1}^{BFGS} ≻ 0$ .

Proof. As in the Key theorem. For $z \neq = 0$ set $a = B_{k}^{1/2} z$ , $b = B_{k}^{1/2} s_{k}$ (square root exists by the spectral theorem 01.01.13); then $z^{⊤} B_{k + 1} z = (∥ a ∥^{2} - (a^{⊤} b)^{2} /∥ b ∥^{2}) + (y_{k}^{⊤} z)^{2} / (y_{k}^{⊤} s_{k})$ . Cauchy-Schwarz makes the first summand $\geq 0$ with equality only if $z = λ s_{k}$ , $λ \neq = 0$ ; in that case $y_{k}^{⊤} z = λ y_{k}^{⊤} s_{k} \neq = 0$ makes the second summand strictly positive. Hence $z^{⊤} B_{k + 1} z > 0$ . $□$

Proposition 2 (curvature condition is necessary for a positive-definite secant update). If $B_{k + 1} ≻ 0$ satisfies $B_{k + 1} s_{k} = y_{k}$ , then $s_{k}^{⊤} y_{k} > 0$ .

Proof. Left-multiply the secant equation by $s_{k}^{⊤}$ : $s_{k}^{⊤} y_{k} = s_{k}^{⊤} B_{k + 1} s_{k} > 0$ because $B_{k + 1} ≻ 0$ and $s_{k} \neq = 0$ (else $s_{k}^{⊤} y_{k} = 0$ and no step was taken). $□$

Proposition 3 (SR1 satisfies the secant equation and is the unique symmetric rank-one secant update). With $w_{k} = y_{k} - B_{k} s_{k}$ and $w_{k}^{⊤} s_{k} \neq = 0$ , the matrix $B_{k + 1} = B_{k} + w_{k} w_{k}^{⊤} / (w_{k}^{⊤} s_{k})$ is the unique symmetric matrix of the form $B_{k} + β u u^{⊤}$ satisfying $B_{k + 1} s_{k} = y_{k}$ .

Proof. Existence: $B_{k + 1} s_{k} = B_{k} s_{k} + w_{k} (w_{k}^{⊤} s_{k}) / (w_{k}^{⊤} s_{k}) = B_{k} s_{k} + w_{k} = B_{k} s_{k} + (y_{k} - B_{k} s_{k}) = y_{k}$ . Uniqueness: any symmetric rank-one secant update has the form $B_{k} + β u u^{⊤}$ with $(B_{k} + β u u^{⊤}) s_{k} = y_{k}$ , i.e. $β (u^{⊤} s_{k}) u = y_{k} - B_{k} s_{k} = w_{k}$ . Thus $u$ is parallel to $w_{k}$ , say $u = w_{k}$ (absorbing scale into $β$ ), and $β (w_{k}^{⊤} s_{k}) = 1$ forces $β = 1/ (w_{k}^{⊤} s_{k})$ . $□$

Proposition 4 (DFP and BFGS are dual). The DFP update of $B$ has the same algebraic form as the BFGS update of $H = B^{- 1}$ under the interchange $B \leftrightarrow H$ , $s \leftrightarrow y$ ; consequently $(B_{k + 1}^{BFGS})^{- 1} = H_{k + 1}^{BFGS}$ as displayed, and $(B_{k + 1}^{DFP})^{- 1} = H_{k + 1}^{DFP}$ .

Proof. Apply the Sherman-Morrison-Woodbury formula $(M + U C V)^{- 1} = M^{- 1} - M^{- 1} U (C^{- 1} + V M^{- 1} U)^{- 1} V M^{- 1}$ to the rank-two BFGS update $B_{k + 1} = B_{k} - \frac{B _{k} s _{k} s _{k}^{⊤} B _{k}}{s _{k}^{⊤} B _{k} s _{k}} + \frac{y _{k} y _{k}^{⊤}}{y _{k}^{⊤} s _{k}}$ , grouping the two rank-one corrections as a rank-two $U C V$ with $U = [B_{k} s_{k} y_{k}]$ . The inversion yields, after simplification using $ρ_{k} = 1/ (y_{k}^{⊤} s_{k})$ , the congruence form $H_{k + 1} = (I - ρ_{k} s_{k} y_{k}^{⊤}) H_{k} (I - ρ_{k} y_{k} s_{k}^{⊤}) + ρ_{k} s_{k} s_{k}^{⊤}$ . Comparing this expression for $H_{k + 1}$ with the DFP formula for $B_{k + 1}$ shows they are identical under $B \leftrightarrow H$ , $s \leftrightarrow y$ ; the verification $H_{k + 1} y_{k} = s_{k}$ is the computation of Exercise 5. $□$

Proposition 5 (BFGS trace/determinant identities and the Powell function). The BFGS update obeys $det (B_{k + 1}) = det (B_{k}) (y_{k}^{⊤} s_{k}) / (s_{k}^{⊤} B_{k} s_{k})$ and $tr (B_{k + 1}) = tr (B_{k}) - ∥ B_{k} s_{k} ∥^{2} / (s_{k}^{⊤} B_{k} s_{k}) + ∥ y_{k} ∥^{2} / (y_{k}^{⊤} s_{k})$ , so the Powell function $ψ (B) = tr (B) - ln det (B)$ changes by a quantity bounded in terms of the cosines of the angles between $s_{k}$ , $B_{k} s_{k}$ , and $y_{k}$ .

Proof. The determinant identity follows from the matrix-determinant lemma applied twice to the rank-one corrections, or from the factorisation $B_{k + 1} = B_{k}^{1/2} (I - \hat{b} \hat{b}^{⊤} + (y_{k} y_{k}^{⊤}) / (y_{k}^{⊤} s_{k}) conjugated) B_{k}^{1/2}$ where $\hat{b} = b /∥ b ∥$ , $b = B_{k}^{1/2} s_{k}$ : the projector $I - \hat{b} \hat{b}^{⊤}$ has eigenvalues $1$ (multiplicity $n - 1$ ) and $0$ , and the added rank-one term restores a single eigenvalue equal to $(y_{k}^{⊤} s_{k}) / (s_{k}^{⊤} B_{k} s_{k})$ , giving the stated determinant ratio. The trace identity is immediate from linearity of the trace applied to the three terms, using $tr (B_{k} s_{k} s_{k}^{⊤} B_{k}) = ∥ B_{k} s_{k} ∥^{2}$ and $tr (y_{k} y_{k}^{⊤}) = ∥ y_{k} ∥^{2}$ . Substituting both into $ψ (B_{k + 1}) - ψ (B_{k})$ and writing $m_{k} = (s_{k}^{⊤} B_{k} s_{k}) / (s_{k}^{⊤} s_{k})$ , $cos θ_{k} = (s_{k}^{⊤} B_{k} s_{k}) / (∥ s_{k} ∥∥ B_{k} s_{k} ∥)$ expresses the change in $ψ$ in terms of these angle and curvature ratios, which remain bounded under the level-set Hessian bounds — the inequality that drives the global-convergence proof. $□$

Proposition 6 (Dennis-Moré: superlinear convergence under unit steps). Under $x_{k} \to x^{*}$ , $\nabla f (x^{*}) = 0$ , $\nabla^{2} f (x^{*}) =: H^{*} ≻ 0$ , $\nabla^{2} f$ Lipschitz near $x^{*}$ , and unit steps $x_{k + 1} = x_{k} - B_{k}^{- 1} g_{k}$ with $B_{k}$ nonsingular, the convergence is q-superlinear if and only if $lim_{k} ∥ (B_{k} - H^{*}) s_{k} ∥/∥ s_{k} ∥ = 0$ .

Proof. The unit step gives $B_{k} s_{k} = - g_{k}$ , and $y_{k} = \overline{H}_{k} s_{k}$ with $\overline{H}_{k} = \int_{0}^{1} \nabla^{2} f (x_{k} + t s_{k}) d t \to H^{*}$ . Then

(B_{k} - H^{*}) s_{k} = - g_{k} - H^{*} s_{k} = - (g_{k} + H^{*} s_{k}) .

Since $g_{k + 1} = g_{k} + y_{k} = g_{k} + \overline{H}_{k} s_{k}$ and $g_{k + 1} = H^{*} e_{k + 1} + o (∥ e_{k + 1} ∥)$ with $g_{k} = H^{*} e_{k} + o (∥ e_{k} ∥)$ , subtracting yields $g_{k + 1} = (B_{k} - H^{*}) s_{k} + (\overline{H}_{k} - H^{*}) s_{k} + o (\cdot)$ after collecting the unit-step identity, so

∥ H^{*} e_{k + 1} ∥ \leq ∥ (B_{k} - H^{*}) s_{k} ∥ + ∥ \overline{H}_{k} - H^{*} ∥ ∥ s_{k} ∥ + o (∥ e_{k} ∥) .

The Lipschitz bound makes $∥ \overline{H}_{k} - H^{*} ∥ = O (∥ e_{k} ∥ + ∥ s_{k} ∥) \to 0$ , so dividing by $∥ s_{k} ∥$ (comparable to $∥ e_{k} ∥$ near the solution) shows $∥ e_{k + 1} ∥/∥ e_{k} ∥ \to 0$ exactly when $∥ (B_{k} - H^{*}) s_{k} ∥/∥ s_{k} ∥ \to 0$ . The reverse implication runs the same identity backward: superlinearity $∥ e_{k + 1} ∥ = o (∥ e_{k} ∥)$ forces $∥ H^{*} e_{k + 1} ∥ = o (∥ s_{k} ∥)$ , whence $∥ (B_{k} - H^{*}) s_{k} ∥/∥ s_{k} ∥ \to 0$ . $□$

Connections Master

Newton's method for optimization 44.03.03 is the parent construction quasi-Newton approximates: where Newton forms and solves $\nabla^{2} f (x_{k}) p = - g_{k}$ with the exact Hessian, quasi-Newton substitutes the secant-updated $B_{k}$ , trading the quadratic rate for the superlinear rate of the Dennis-Moré theorem while eliminating second derivatives entirely. The descent property that Newton derives from $\nabla^{2} f (x^{*}) ≻ 0$ becomes here the hereditary positive-definiteness of BFGS, and the modified-Newton constructions that repair an indefinite exact Hessian have their quasi-Newton counterpart in SR1, which instead embraces indefiniteness for trust-region use.
Line-search methods and the Wolfe conditions 44.03.01 supply the single hypothesis the whole theory turns on: the Wolfe curvature condition forces $s_{k}^{⊤} y_{k} > 0$ , which is exactly the condition under which a positive-definite secant update exists (Proposition 2), so the line search and the secant update are not independent components but a matched pair. The Zoutendijk angle-condition machinery of that unit is what converts BFGS's hereditary positive-definiteness into the global-convergence theorem, since a positive-definite $B_{k}$ keeps the search direction angle-bounded away from orthogonality to the gradient.
The spectral theorem for symmetric operators 01.01.13 is the algebraic engine of the positive-definiteness proofs: the symmetric square root $B_{k}^{1/2}$ used in the hereditary-positivity argument, the eigenvalue analysis behind the trace-determinant identities and the Powell function, and the very statement that $B_{k} ≻ 0$ means all eigenvalues are positive all rest on it. Multivariable Taylor expansion 02.05.05 provides the average-Hessian identity $y_{k} = (\int_{0}^{1} \nabla^{2} f (x_{k} + t s_{k}) d t) s_{k}$ that interprets the secant equation as average-curvature matching and powers the Dennis-Moré error recursion.
Limited-memory L-BFGS 44.03.05, nonlinear conjugate gradient 44.03.06, trust-region methods 44.03.02, and Broyden's method for nonlinear equations 43.02.03 are the downstream consumers and siblings: L-BFGS stores only the last $m$ secant pairs $(s_{i}, y_{i})$ to apply $H_{k} g_{k}$ implicitly in $O (mn)$ for large $n$ , the Broyden-class conjugate-direction property makes BFGS with exact line search coincide with linear CG on a quadratic, SR1 is the indefiniteness-tolerant Hessian model inside trust regions, and the nonsymmetric Jacobian version of the secant update is exactly Broyden's root-finding method. Quasi-Newton is thus the hub from which large-scale smooth optimization radiates.

Historical & philosophical context Master

The quasi-Newton idea originated with William C. Davidon in 1959, a physicist at Argonne National Laboratory who, frustrated by unreliable derivative-free methods on a coordinate-descent code, devised a "variable metric" method that builds a Hessian model from successive gradients; his report went unpublished for decades and appeared only in 1991 ^{[Davidon 1959]}. Roger Fletcher and Michael Powell recast and popularised Davidon's method in 1963, producing what is now the DFP update ^{[Fletcher-Powell 1963]}. The superior BFGS update was discovered independently in 1970 by Charles Broyden, Roger Fletcher, Donald Goldfarb, and David Shanno, four authors whose initials name it, each arriving at the same rank-two update from a different motivation — least-change, duality with DFP, and self-scaling among them.

The theoretical foundations were consolidated by John Dennis and Jorge Moré, whose 1977 survey Quasi-Newton methods, motivation and theory established the least-change variational characterisation and the superlinear-convergence condition that bears their names ^{[Dennis-More 1977]}, and by the textbook treatments of Dennis and Schnabel and of Nocedal and Wright, the latter giving the global-convergence analysis of BFGS via the Powell function. The symmetric rank-one update, though older as a formula, was rehabilitated for trust-region use by Conn, Gould, and Toint in the late 1980s when its convergence-to-the-true-Hessian property was proved under the skipping safeguard ^{[Conn-Gould-Toint 1991]}. The limited-memory variant L-BFGS, due to Jorge Nocedal in 1980, made the method the default for large-scale smooth optimization and machine learning ^{[Nocedal 1980]}.

Bibliography Master

@book{nocedalwright2006,
  author    = {Nocedal, Jorge and Wright, Stephen J.},
  title     = {Numerical Optimization},
  edition   = {2},
  series    = {Springer Series in Operations Research and Financial Engineering},
  publisher = {Springer},
  year      = {2006}
}

@book{dennisschnabel1996,
  author    = {Dennis, John E. and Schnabel, Robert B.},
  title     = {Numerical Methods for Unconstrained Optimization and Nonlinear Equations},
  series    = {Classics in Applied Mathematics},
  volume    = {16},
  publisher = {SIAM},
  year      = {1996},
  note      = {Reprint of the 1983 Prentice-Hall edition}
}

@article{dennismore1977,
  author  = {Dennis, John E. and Mor\'{e}, Jorge J.},
  title   = {Quasi-Newton methods, motivation and theory},
  journal = {SIAM Review},
  volume  = {19},
  number  = {1},
  year    = {1977},
  pages   = {46--89}
}

@article{fletcherpowell1963,
  author  = {Fletcher, Roger and Powell, Michael J. D.},
  title   = {A rapidly convergent descent method for minimization},
  journal = {The Computer Journal},
  volume  = {6},
  number  = {2},
  year    = {1963},
  pages   = {163--168}
}

@techreport{davidon1959,
  author      = {Davidon, William C.},
  title       = {Variable metric method for minimization},
  institution = {Argonne National Laboratory},
  number      = {ANL-5990 (Rev.)},
  year        = {1959},
  note        = {Reprinted in SIAM Journal on Optimization 1 (1991), 1--17}
}

@article{conngouldtoint1991,
  author  = {Conn, Andrew R. and Gould, Nicholas I. M. and Toint, Philippe L.},
  title   = {Convergence of quasi-Newton matrices generated by the symmetric rank one update},
  journal = {Mathematical Programming},
  volume  = {50},
  number  = {1--3},
  year    = {1991},
  pages   = {177--195}
}

@article{nocedal1980,
  author  = {Nocedal, Jorge},
  title   = {Updating quasi-Newton matrices with limited storage},
  journal = {Mathematics of Computation},
  volume  = {35},
  number  = {151},
  year    = {1980},
  pages   = {773--782}
}

Prerequisites

44.03.03
44.03.01
01.01.13

Tier anchors

beginner: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §2.2 and §6.1 (the quasi-Newton idea: build a curvature model from successive gradients instead of computing second derivatives, the secant picture in one dimension as the slope of the gradient between two points); Boyd & Vandenberghe 2004 Convex Optimization (Cambridge) §9.7 (the quasi-Newton method as a cheap Newton surrogate)
intermediate: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §6.1 (the secant equation $B_{k + 1} s_{k} = y_{k}$ , the curvature condition $s_{k}^{⊤} y_{k} > 0$ , the DFP and BFGS rank-two updates and their inverse forms via Sherman-Morrison-Woodbury, hereditary positive-definiteness); Dennis & Schnabel 1996 Numerical Methods for Unconstrained Optimization and Nonlinear Equations (SIAM) §9.1-9.2 (the least-change secant-update derivation, the Broyden class, and the local superlinear-convergence theory)
master: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §6.1-6.4 and §3.4 (the Broyden class, SR1 and its indefiniteness handling, the Dennis-Moré characterisation of superlinear convergence, the self-correcting property of BFGS, and the global-convergence theorem for BFGS with Wolfe line search); Dennis & Schnabel 1996 Numerical Methods for Unconstrained Optimization and Nonlinear Equations (SIAM) §9; Dennis & Moré 1977 Quasi-Newton methods, motivation and theory (SIAM Review)

References

Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.) · Springer Series in Operations Research and Financial Engineering (2006). Chapter 6 'Quasi-Newton Methods', §6.1-6.4: quasi-Newton methods replace the exact Hessian solve $\nabla^{2} f (x_{k}) p = - \nabla f (x_{k})$ of Newton's method by maintaining an approximation $B_{k} \approx \nabla^{2} f (x_{k})$ (or its inverse $H_{k} \approx \nabla^{2} f (x_{k})^{- 1}$ ) updated from gradient differences. The secant equation $B_{k + 1} s_{k} = y_{k}$ with $s_{k} = x_{k + 1} - x_{k}$ , $y_{k} = \nabla f (x_{k + 1}) - \nabla f (x_{k})$ , enforcing that $B_{k + 1}$ reproduces the average curvature along the last step; the curvature condition $s_{k}^{⊤} y_{k} > 0$ required for a positive-definite secant update, guaranteed by the Wolfe line search. The DFP update $B_{k + 1} = (I - ρ_{k} y_{k} s_{k}^{⊤}) B_{k} (I - ρ_{k} s_{k} y_{k}^{⊤}) + ρ_{k} y_{k} y_{k}^{⊤}$ with $ρ_{k} = 1/ (y_{k}^{⊤} s_{k})$ and the BFGS update $B_{k + 1} = B_{k} - \frac{B _{k} s _{k} s _{k}^{⊤} B _{k}}{s _{k}^{⊤} B _{k} s _{k}} + \frac{y _{k} y _{k}^{⊤}}{y _{k}^{⊤} s _{k}}$ , dual under the $B \leftrightarrow H$ , $s \leftrightarrow y$ interchange; the inverse-Hessian forms $H_{k + 1}^{BFGS} = (I - ρ_{k} s_{k} y_{k}^{⊤}) H_{k} (I - ρ_{k} y_{k} s_{k}^{⊤}) + ρ_{k} s_{k} s_{k}^{⊤}$ obtained via the Sherman-Morrison-Woodbury formula so each step costs $O (n^{2})$ with no linear solve. Hereditary positive-definiteness of BFGS: $B_{k} ≻ 0$ and $s_{k}^{⊤} y_{k} > 0 \Rightarrow B_{k + 1} ≻ 0$ . The symmetric rank-one (SR1) update $B_{k + 1} = B_{k} + \frac{( y _{k} - B _{k} s _{k} ) ( y _{k} - B _{k} s _{k} ) ^{⊤}}{( y _{k} - B _{k} s _{k} ) ^{⊤} s _{k}}$ which can build indefinite approximations and so suits trust-region use but loses positive-definiteness; the safeguard skipping the update when $∣ (y_{k} - B_{k} s_{k})^{⊤} s_{k} ∣ < r ∥ s_{k} ∥∥ y_{k} - B_{k} s_{k} ∥$ . The Broyden class $B_{k + 1}^{ϕ} = (1 - ϕ) B_{k + 1}^{BFGS} + ϕ B_{k + 1}^{DFP}$ . Local superlinear convergence and the Dennis-Moré condition $lim_{k} ∥ (B_{k} - \nabla^{2} f (x^{*})) s_{k} ∥/∥ s_{k} ∥ = 0$ as the exact characterisation of superlinearity; the self-correcting property of BFGS; global convergence of BFGS with Wolfe line search on convex objectives. Motivation for limited-memory L-BFGS storing only the last $m$ pairs $(s_{i}, y_{i})$ .
Dennis, J. E. & Schnabel, R. B. — Numerical Methods for Unconstrained Optimization and Nonlinear Equations · SIAM Classics in Applied Mathematics 16 (1996, reprint of the 1983 Prentice-Hall edition). Chapter 9 'Secant Methods for Unconstrained Minimization' develops the least-change secant-update viewpoint: among all symmetric matrices satisfying the secant equation $B_{k + 1} s_{k} = y_{k}$ , BFGS and DFP are the solutions of a weighted-Frobenius least-change problem $min ∥ W^{1/2} (B_{k + 1} - B_{k}) W^{1/2} ∥_{F}$ for an appropriate weight $W$ (the average Hessian for the affine-invariant derivation), and SR1 is the unique symmetric rank-one secant update. The book proves bounded deterioration of the approximation, local q-superlinear convergence of the BFGS and DFP iterations under a Lipschitz Hessian at a strong minimiser, and presents the Dennis-Moré theorem characterising superlinear convergence by the condition that the step asymptotically agrees with the Newton step. The Broyden class for nonlinear-equation rootfinding (the Jacobian-update analogue) is treated in Chapter 8 and specialised to the symmetric optimization setting in Chapter 9.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m