Learning path

Full curriculum

Full curriculum

Unit content

Newton's method for unconstrained optimization

Gradient descent uses only local slope. Newton's method for optimization also uses local curvature.

Near the current point $x_k$, approximate the objective by

$$f(x_k+d)\approx f(x_k)+\nabla f(x_k)^Td+\frac12 d^T H_f(x_k)d.$$

Minimizing this quadratic model gives the Newton step $d_k$ from

$$H_f(x_k)d_k=-\nabla f(x_k),$$

followed by

$$x_{k+1}=x_k+d_k$$

or by a shortened step when the full Newton step is not appropriate.

Near a well-behaved strict local minimum, Newton iterations can converge very quickly. Far from a solution, the linear system for the Newton step may fail to determine a useful direction, especially when the Hessian is indefinite.

Second-order methods trade more expensive iterations for richer local information.