mathematics//optimization//Newton's method

Newton's method is an iterative algorithm that finds a zero of a function, or a minimum of a cost, by replacing the function at the current point with its linear approximation (for a minimum, the quadratic one), solving that approximation exactly and repeating from the answer; it is the workhorse inside power-flow calculations of the grid, circuit simulators, the interior-point solvers of MPC and the optimizers of SLAM. For a root of \(f\) the step is \(x_{k+1}=x_k-f(x_k)/f'(x_k)\). Taking \(f(x)=x^2-2\) and starting at 1.5 gives 1.41667 and then 1.414216, against \(\sqrt2=1.4142136\): near the solution the number of correct digits roughly doubles at every iteration.

Newton's method is an iterative algorithm that finds a zero of a function, or a minimum of a cost, by replacing the function at the current point with its linear approximation (for a minimum, the quadratic one), solving that approximation exactly and repeating from the answer; it is the workhorse inside power-flow calculations of the grid, circuit simulators, the interior-point solvers of MPC and the optimizers of SLAM. For a root of fff the step is xk+1=xk−f(xk)/f′(xk)x_{k+1}=x_k-f(x_k)/f'(x_k)xk+1​=xk​−f(xk​)/f′(xk​). Taking f(x)=x2−2f(x)=x^2-2f(x)=x2−2 and starting at 1.5 gives 1.41667 and then 1.414216, against 2=1.4142136\sqrt2=1.41421362​=1.4142136: near the solution the number of correct digits roughly doubles at every iteration.

To minimize a cost L(θ)L(\theta)L(θ), the method is applied to the gradient, whose zero is the minimum, and the derivative of the gradient is the Hessian HHH.

θk+1=θk−H(θk)−1 ∇L(θk)\theta_{k+1} = \theta_k - H(\theta_k)^{-1}\,\nabla L(\theta_k)θk+1​=θk​−H(θk​)−1∇L(θk​)

The Hessian rescales every direction by its curvature. On a quadratic bowl one step lands at the bottom, however elongated the bowl, where gradient descent would zigzag across a narrow valley for hundreds of steps.

Newton's method is the pure form of linearize, solve, repeat: it trusts the linearization only near the current point and makes a new one as soon as it moves. That trust is justified close to the solution and can be badly wrong far from it.

Far from the solution a full step can overshoot or head toward a maximum or a saddle point, where the Hessian is not positive definite. Practical solvers damp the step with a line search or limit it to a trust region, and fall back toward gradient steps when the quadratic model is poor (the idea of the Levenberg-Marquardt algorithm in nonlinear least squares).

The price is the Hessian. It has n2n^2n2 entries and solving with it costs of the order of n3n^3n3, harmless for the dozens of variables of an MPC and impossible for the millions of a neural network. Quasi-Newton methods (BFGS, and L-BFGS, which keeps only a few recent gradient pairs) estimate the curvature from successive gradients and correct the zigzag at a fraction of the cost; they are the default for medium-sized smooth problems in scientific libraries.

The same move runs elsewhere under other names: the extended Kalman filter linearizes the model at each step, and Gauss-Newton linearizes the residuals of a fit. The pattern is gathered in linearize-solve-repeat.