Second-order methods · Definition
Newton's method for optimization
Before you start you need to know
Gradient descent uses only first derivatives and moves with fixed or tuned steps. Newton's method incorporates curvature to choose a more informed step.
Definition
Newton's method for optimization is an iterative algorithm that seeks a critical point of a differentiable function \(f:\mathbb{R}^n\to\mathbb{R}\) using the gradient \(\nabla f\) and the Hessian \(H_f\).
If the Hessian \(H_f(x_k)\) is positive definite, the Newton step is the minimizer of the second-order quadratic model of \(f\) around \(x_k\). Near a minimizer with invertible Hessian, convergence is quadratic, meaning the number of correct digits roughly doubles at each iteration.
Consider \(f(x,y)=x^2+4y^2\) with \(x_0=(2,1)\). Its gradient is \((2x,8y)\) and its Hessian is \(\mathrm{diag}(2,8)\), so a single step reaches \((0,0)\), the global minimum.
A typical mistake is computing \(H_f^{-1}\nabla f\) as \(\nabla f\,/\,H_f\) entrywise or forgetting the negative sign. Also, applying the method without checking that the Hessian is positive definite can drive the iteration toward a maximum or a saddle point.
Think about it
Why does Newton's step not need a fixed step size like gradient descent in the quadratic case?
Because the Hessian scales each component by its curvature, so the step already has the right length and reaches the minimum in one iteration.
Exercises 10
- What is the iteration formula of Newton's method for minimizing \(f:\mathbb{R}^n\to\mathbb{R}\)?
- Which condition on the Hessian guarantees that the Newton step is a descent direction?
- If the Hessian is the identity matrix everywhere, what does the Newton step reduce to?
- What type of convergence does Newton's method have near a minimizer with invertible Hessian?
- Which object must be computed at each iteration of Newton's method besides the gradient?
- For \(f(x,y)=x^2+2y^2\) at \((1,1)\), compute the Newton step \(p=-H_f^{-1}\nabla f\).
- For \(f(x,y)=x^4+y^2\) at \((1,2)\), what is the Newton step in the \(x\) coordinate?
- For \(f(x)=e^x-2x\) on \(\mathbb{R}\), what is \(x_1\) starting from \(x_0=0\)?
- For \(f(x,y)=x^2+xy+y^2-3x\), compute the Newton step from \((0,0)\) and verify that the resulting point is the minimizer.
- For \(f(x,y)=x^3-3x+y^2\), what happens if the Newton step is applied from \((0,1)\)? Use the Hessian \(\mathrm{diag}(6x,2)\).
References
- Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
- Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.