Newton's Method
Newton's method uses second-order information (the Hessian) to achieve faster local convergence. It is foundational for interior-point methods and scientific computing.
Key Points
- Newton's method solves $\nabla f(x) = 0$ using local quadratic approximations.
- For strongly convex functions with Lipschitz Hessian, convergence is quadratic near the optimum.
- Quasi-Newton methods (L-BFGS) approximate the Hessian to reduce cost.
Formulas
Newton update
$$x_{k+1} = x_k - [\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$$
Quadratic model
$$m_k(p) = f(x_k) + \nabla f(x_k)^\top p + \frac{1}{2} p^\top \nabla^2 f(x_k) p$$
Code Example
import numpy as np
def f(x):
return x**2 + 4*x + 4
def grad_f(x):
return 2*x + 4
def hess_f(x):
return 2.0
x = 0.0
for _ in range(5):
x -= grad_f(x) / hess_f(x)
print(x) # -2 (exact in one step)