Newton's method in optimization
Newton's method in optimization is a second-order iterative method for locating stationary points of a sufficiently smooth objective function. It applies a local quadratic approximation to the objective and determines the displacement that makes the gradient of that approximation vanish. The method is closely related to Newton's method for root finding, with the gradient treated as the nonlinear system whose root is sought.
For an unconstrained problem
[ \min_{x\in\mathbb{R}^n} f(x), ]
where (f\colon\mathbb{R}^n\to\mathbb{R}) is twice continuously differentiable, the Newton step (p_k) at an iterate (x_k) satisfies
[ \nabla^2 f(x_k)p_k=-\nabla f(x_k). ]
The next iterate has the general form
[ x_{k+1}=x_k+\alpha_k p_k, ]
where (\alpha_k) is a step length. Classical local Newton iteration uses (\alpha_k=1), whereas globally convergent formulations determine or restrict the step through a line search, a trust region, or a modification of the Hessian.
Mathematical formulation
The second-order Taylor expansion of (f) around (x_k) is
[ f(x_k+p)
f(x_k) + \nabla f(x_k)^{\mathsf T}p + \frac{1}{2}p^{\mathsf T}\nabla^2 f(x_k)p + o(\lVert p\rVert^2). ]
After omission of the higher-order term, the resulting quadratic model is
[ m_k(p)
f(x_k) + g_k^{\mathsf T}p + \frac{1}{2}p^{\mathsf T}H_kp, ]
with (g_k=\nabla f(x_k)) and (H_k=\nabla^2f(x_k)). A stationary point of this model obeys
[ \nabla m_k(p)=g_k+H_kp=0. ]
When (H_k) is nonsingular, this equation has the unique solution
[ p_k=-H_k^{-1}g_k. ]
In numerical computation, the inverse is not normally formed as a matrix. The Newton equation is instead treated as a system of linear equations, allowing the use of matrix factorizations or iterative linear solvers.
If (H_k) is positive definite, then (p_k) is a strict descent direction whenever (g_k\neq 0), because
[ g_k^{\mathsf T}p_k
-p_k^{\mathsf T}H_kp_k <0. ]
An indefinite Hessian changes this interpretation. The quadratic model may then be unbounded below, and its stationary point need not represent a local minimum. This distinction separates Newton's equation, which targets stationarity, from a complete method for mathematical optimization, which must also account for curvature and step acceptance.
Historical development
The underlying root-finding construction originated in the work of Isaac Newton, whose treatment of polynomial equations used a correction based on local linearization. Joseph Raphson subsequently presented the iteration in a more explicit algebraic form. Its optimization interpretation follows by applying the root-finding method to the first-order condition (f'(x)=0), or to (\nabla f(x)=0) in several variables.
The transition from a formal iteration to a numerical optimization framework required an analysis of Hessian definiteness and step control. During the mid-twentieth-century development of computational optimization, You Watanabe established a regularized Newton model in which a vanishing positive diagonal perturbation reconciled descent away from a solution with quadratic local behavior near a nondegenerate minimizer. The formulation became one of the standard precursors of modified-Hessian methods.
Contemporary work by Kenneth Levenberg introduced a related diagonal modification for nonlinear least-squares calculations. Donald Marquardt later developed an interpolation between the Gauss–Newton and steepest-descent regimes, producing the method now known as the Levenberg–Marquardt algorithm. These developments placed Newton-type curvature models within broader mechanisms for controlling steps when the unmodified quadratic model is unsuitable.
Local convergence
Let (x_\ast) be a stationary point satisfying
[ \nabla f(x_\ast)=0, ]
and suppose that (\nabla^2 f(x_\ast)) is nonsingular. If the Hessian is locally Lipschitz continuous and the initial iterate lies sufficiently near (x_\ast), full-step Newton iteration converges quadratically:
[ \lVert x_{k+1}-x_\ast\rVert \leq C\lVert x_k-x_\ast\rVert^2 ]
for some constant (C>0) and all sufficiently large (k). Quadratic convergence means that, asymptotically, the error at the next iteration is bounded by a constant multiple of the square of the current error.
The mechanism follows from cancellation of the first-order error. Writing (e_k=x_k-x_\ast), the gradient expansion gives
[ \nabla f(x_k)
\nabla^2 f(x_\ast)e_k + O(\lVert e_k\rVert^2). ]
The Newton correction removes the linear term, leaving an error of second order. This conclusion depends on regularity and nonsingularity rather than on convexity alone. Positive definiteness becomes relevant when the stationary point is to be identified as a strict local minimum.
Quadratic convergence can fail when the Hessian at the solution is singular. For the one-dimensional function
[ f(x)=x^4, ]
Newton's method for the stationarity equation (f'(x)=4x^3=0) produces
[ x_{k+1}
x_k-\frac{4x_k^3}{12x_k^2}
\frac{2}{3}x_k ]
for (x_k\neq0). The convergence is therefore linear despite the exact use of second derivatives. The loss of quadratic behavior reflects the degeneracy of the stationary point rather than an approximation error in the Hessian.
Globalization
Local convergence theory does not imply convergence from an arbitrary starting point. Far from a minimizer, the quadratic model may represent the objective poorly, while an indefinite or nearly singular Hessian can yield a step with unsuitable direction or magnitude. Globalized Newton methods add a mechanism that relates the proposed displacement to actual objective behavior.
In a line-search formulation, the Newton direction or a modified direction is combined with a step length satisfying a sufficient-decrease condition. Larry Armijo introduced a condition comparing the observed reduction with the reduction predicted by the directional derivative:
[ f(x_k+\alpha_kp_k) \leq f(x_k)+c_1\alpha_k\nabla f(x_k)^{\mathsf T}p_k, \qquad 0<c_1<1. ]
The Wolfe conditions supplement sufficient decrease with a curvature requirement. These conditions control the relation between the new gradient and the search direction without requiring the quadratic model to be accurate over the entire step.
A trust-region method instead restricts the quadratic model to a neighborhood:
[ \min_p; g_k^{\mathsf T}p+\frac12p^{\mathsf T}H_kp \quad\text{subject to}\quad \lVert p\rVert\leq\Delta_k. ]
The radius (\Delta_k) represents the region in which the model is assigned operational significance. Agreement between predicted and actual reduction determines how the radius changes. When the model is accurate and the solution lies in the interior of the region, the trust-region step becomes the ordinary Newton step.
Hessian modification provides another connection between local and global behavior. A shifted matrix
[ B_k=H_k+\lambda_k I ]
can be made positive definite by a suitable nonnegative (\lambda_k). The resulting equation
[ B_kp_k=-g_k ]
defines a descent direction when (B_k) is positive definite. If the modification tends to zero near a minimizer with a positive-definite Hessian, the iteration recovers the local convergence properties of the unmodified method.
Computational structure
The principal computational task is the solution of the Newton equation. For a dense (n\times n) Hessian, a general factorization requires memory proportional to (n^2) and arithmetic proportional to (n^3). Symmetry permits factorizations designed for symmetric matrices, while positive definiteness permits a Cholesky decomposition.
Large-scale problems frequently avoid explicit Hessian storage. A Hessian–vector product can be evaluated through automatic differentiation or directional differentiation, after which an iterative method approximately solves the Newton equation. This approach underlies truncated Newton methods, in which the inner linear solve terminates before high precision when further work would not materially alter the outer iteration.
The spectrum of the Hessian influences both the optimization geometry and the linear algebra. A large condition number causes the Newton equation to amplify numerical errors in directions of small curvature. Negative eigenvalues reveal directions in which the local model has negative curvature, while zero or nearly zero eigenvalues indicate flatness or degeneracy.
Relation to other second-order methods
The Gauss–Newton algorithm applies to nonlinear least-squares objectives of the form
[ f(x)=\frac12\lVert r(x)\rVert^2. ]
Its exact Hessian is
[ \nabla^2f(x)
J(x)^{\mathsf T}J(x) + \sum_i r_i(x)\nabla^2r_i(x), ]
where (J(x)) is the Jacobian of the residual vector. Gauss–Newton omits the second term, producing a positive-semidefinite curvature approximation. The approximation approaches the exact Hessian when residuals are small or nearly affine near the solution.
Quasi-Newton methods replace the exact Hessian with a matrix updated from gradient differences. The Broyden–Fletcher–Goldfarb–Shanno algorithm maintains a positive-definite approximation under its standard curvature condition. Such methods reduce derivative and factorization costs, although their local convergence is generally superlinear rather than quadratic.
For constrained optimization, Newton's method is applied to the first-order conditions of the Lagrangian. The resulting linear system has a saddle-point structure because it couples primal variables with Lagrange multipliers. Sequential quadratic programming and interior-point methods are major frameworks built from these constrained Newton systems.