Recipe

Run one BFGS update step

Use when: you're minimizing f with a current point x^{(k)}, its gradient g_k, and an inverse-Hessian approximation B_k — no true Hessian computed

Goal: the next point x^{(k+1)} and an updated approximation B_{k+1} that matches the curvature just observed

Taught in Quasi-Newton methods: DFP and BFGS

1. 1

   Multiply the current inverse-Hessian approximation by the current gradient, then negate. B_0 is commonly the identity, which makes the first step an ordinary gradient-descent step.

   Example

   For f(x,y)=x^2+\tfrac12y^2 from x^{(0)}=(1,1) with B_0=I: \nabla f=(2x,y) gives g_0=(2,1), so p_0=-B_0g_0=(-2,-1).

   Why: -B_kg_k is exactly what -H^{-1}\nabla f would be if B_k were the true inverse Hessian — the quasi-Newton stand-in for Newton's own step direction.

2. 2

   Choose a step length \alpha_k along p_k, then set x^{(k+1)}=x^{(k)}+\alpha_kp_k.

   Example

   Exact line search for this quadratic f: \alpha_0=-\dfrac{g_0^\top p_0}{p_0^\top Hp_0}=\dfrac59\approx0.5556 (checking against the true H only to verify here — BFGS itself never needs H). So x^{(1)}=x^{(0)}+\alpha_0p_0\approx(-0.1111,\,0.4444).

   • an exact line search is cheap to run (small problem, or f well-approximated as quadratic) — use it directly, as this worked example does.
   • an exact line search isn't practical — fall back to a backtracking line search, choosing \alpha_k small enough to guarantee f actually decreases.

   Why: a poorly chosen \alpha_k can make y_k^\top s_k\le0 in the next step, which breaks BFGS's guarantee of staying positive definite.

3. 3

   Set s_k=x^{(k+1)}-x^{(k)} and y_k=\nabla f(x^{(k+1)})-\nabla f(x^{(k)}), then \rho_k=1/(y_k^\top s_k).

   Example

   g_1=(2x^{(1)}_1,x^{(1)}_2)\approx(-0.2222,\,0.4444). s_0=x^{(1)}-x^{(0)}\approx(-1.1111,-0.5556), y_0=g_1-g_0\approx(-2.2222,-0.5556), and \rho_0=1/(y_0^\top s_0)\approx0.36.

   Why: s_k and y_k are the only new information this step reveals about f's curvature — the whole BFGS update below is built from these two vectors alone, with no second derivative evaluated anywhere.

4. 4

   Plug s_k,y_k,\rho_k,B_k into B_{k+1}=(I-\rho_ks_ky_k^\top)B_k(I-\rho_ky_ks_k^\top)+\rho_ks_ks_k^\top.

   Example

   Plugging s_0,y_0,\rho_0,B_0=I in gives B_1\approx\begin{bmatrix}0.5062&-0.0247\\-0.0247&1.0988\end{bmatrix}\approx H^{-1}=\begin{bmatrix}0.5&0\\0&1\end{bmatrix}, already close after a single update.

   Why: this rank-2 correction is forced to satisfy the secant condition B_{k+1}y_k=s_k exactly, which is what guarantees the approximation keeps improving toward the true H^{-1} as more steps accumulate.