Page 04: Newton's Method and BFGS

The Hessian is the matrix of second partial derivatives:

$$\nabla^2 f = \begin{bmatrix} \frac{\partial^2 f}{\partial x^2} & \frac{\partial^2 f}{\partial x \partial y} \\ \frac{\partial^2 f}{\partial y \partial x} & \frac{\partial^2 f}{\partial y^2} \end{bmatrix}$$

Gradient = first derivatives = slope (direction). Hessian = second derivatives = curvature (how fast the slope changes).

$\nabla^2 f$

The Hessian matrix: collects all second partial derivatives of $f$

$\frac{\partial^2 f}{\partial x^2}$

Curvature in the $x$ direction (how fast the $x$-slope is changing)

$\frac{\partial^2 f}{\partial y^2}$

Curvature in the $y$ direction

$\frac{\partial^2 f}{\partial x \partial y}$

Cross-curvature: how the $x$-slope changes as you move in $y$ (off-diagonal entries; zero for separable functions)

For $f(x,y) = x^2 + 3y^2$: $\nabla^2 f = \begin{bmatrix}2&0\\0&6\end{bmatrix}$

Curvature in x is 2 (gentle), curvature in y is 6 (steep). The Hessian captures this difference; GD cannot.

Newton's update:

$$p_k = -[\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$$

In English: "invert the Hessian, multiply by the gradient, negate."

Compare to GD: $p_k = -\alpha \cdot \nabla f(x_k)$

$p_k$

The Newton step: the direction and distance to move from the current point

$\nabla^2 f(x_k)$

The Hessian at the current point $x_k$; captures curvature in every direction

$[\nabla^2 f(x_k)]^{-1}$

The inverse Hessian; converts the gradient into a curvature-scaled step (big steps where gentle, small steps where steep)

$\nabla f(x_k)$

The gradient at $x_k$; points in the direction of steepest ascent

$-$

Negate so we step downhill (opposite to the gradient direction)

Newton replaces the fixed $\alpha$ with the inverse Hessian $[\nabla^2 f]^{-1}$. The Hessian automatically scales each direction by its curvature. No step size needed!

BFGS update (from Assignment 2):

$$H_{k+1} = (I - \rho_k s_k y_k^T) H_k (I - \rho_k y_k s_k^T) + \rho_k s_k s_k^T$$

$H_{k+1}$

The updated inverse-Hessian approximation (what we are computing)

$H_k$

The current inverse-Hessian approximation; starts as $I$ (identity) and improves each iteration

$s_k$

$= x_{k+1} - x_k$: the step we just took (position change)

$y_k$

$= g_{k+1} - g_k$: how the gradient changed after that step (tells us about curvature along $s_k$)

$\rho_k$

$= 1/(y_k^T s_k)$: a scalar normalizing factor that keeps the update well-scaled

$I$

The identity matrix; the "do nothing" starting point before BFGS learns any curvature

$s_k y_k^T$

An outer product (rank-1 matrix) encoding the relationship between the step and the gradient change

Key idea: You learn about the curvature from how the gradient CHANGED when you took a step. If the gradient changed a lot → high curvature. If it barely changed → low curvature.