Newton's Method for Optimization

Use the Hessian to model local curvature and jump to the minimum of a quadratic approximation, achieving quadratic convergence near the optimum.

Second-order steps

Gradient descent uses only the slope; Newton's method also uses curvature. It approximates the objective near x_k by a quadratic using the gradient and Hessian, then moves to that quadratic's minimizer. The update is x_{k+1} = x_k - H(x_k)^{-1} grad f(x_k), where H is the Hessian of second derivatives.

Quadratic convergence

Near a minimum where the Hessian is positive definite, Newton's method converges quadratically: the number of correct digits roughly doubles each iteration. This is dramatically faster than the linear convergence of gradient descent, which is the main reason to pay the cost of computing and inverting the Hessian.

Costs and cautions

• Each step forms the n-by-n Hessian and solves a linear system, costing O(n^3) in general.
• Far from the optimum the pure Newton step can diverge or move toward a saddle if the Hessian is indefinite.
• A line search or trust region is added to make it globally reliable (damped Newton).

Handling indefinite Hessians

When the Hessian is not positive definite, the Newton direction may not be a descent direction. Practical remedies modify the Hessian to be positive definite (adding a multiple of the identity), or switch to a trust-region subproblem that remains well posed even with negative curvature.

When to use it

Newton's method shines when the dimension is moderate, the Hessian is available or cheap, and high accuracy is needed. For high-dimensional machine learning, forming the Hessian is impractical, so quasi-Newton methods that approximate it are preferred.

import numpy as np
def newton(grad, hess, x, iters=20):
    for _ in range(iters):
        x = x - np.linalg.solve(hess(x), grad(x))
    return x

Newton and quasi-Newton solvers converge design-optimization loops in few iterations when each expensive physics evaluation must be used sparingly.