Truncated Newton method

The truncated Newton method is an iterative technique for solving large-scale nonlinear optimization problems. It approximates the step of Newton's method by terminating the solution of the Newton equations before full numerical accuracy is reached. The resulting method is also called a Newton–Krylov method or, when conjugate gradients form the inner iteration, a Newton–CG method.

For a twice continuously differentiable objective function

[ f:\mathbb{R}^n\rightarrow\mathbb{R}, ]

an unconstrained minimizer satisfies the first-order condition

[ \nabla f(x)=0. ]

At an iterate (x_k), the exact Newton direction (p_k) is defined by

[ \nabla^2 f(x_k)p_k=-\nabla f(x_k). ]

A truncated Newton method replaces the exact solution of this linear system with an approximate vector obtained from a Krylov subspace. The inner iteration ends when its residual is sufficiently small, when a direction of nonpositive curvature is encountered, or when a trust region boundary restricts further motion. The word “truncated” therefore refers to the incomplete linear solve rather than to a truncated expansion of the objective function.

Mathematical formulation

Let

[ g_k=\nabla f(x_k),\qquad H_k=\nabla^2 f(x_k). ]

The inner linear solver produces (p_k) satisfying

[ H_kp_k=-g_k+r_k, ]

where (r_k) is the residual of the Newton equation. A common analytical condition has the form

[ \lVert r_k\rVert\leq \eta_k\lVert g_k\rVert, \qquad 0\leq \eta_k<1, ]

with (\eta_k) known as a forcing term. A fixed forcing term generally yields linear local convergence, whereas a sequence satisfying (\eta_k\rightarrow 0) supports superlinear convergence under the standard regularity assumptions. Quadratic convergence is recovered when the residual decreases at a rate comparable to the gradient norm and the Hessian is locally Lipschitz continuous.

The approximate step belongs to the subspace

[ \mathcal K_j(H_k,-g_k)

\operatorname{span} \left{ -g_k,, -H_kg_k,, \ldots,, -H_k^{j-1}g_k \right}. ]

This representation permits the inner method to use Hessian–vector products without storing the full Hessian matrix. For a smooth objective, such a product can be approximated by

[ H_kv \approx \frac{\nabla f(x_k+h v)-\nabla f(x_k)}{h}, ]

although automatic differentiation and analytic directional derivatives provide alternative realizations. Methods based exclusively on these products are classified as matrix-free methods.

Historical development

The method developed from the interaction between Newton iteration and Krylov-subspace linear algebra. Magnus Hestenes and Eduard Stiefel established the conjugate-gradient method in the early 1950s, providing a finite-dimensional procedure for positive-definite linear systems. Its later use inside nonlinear optimization transformed the Newton equation from a direct factorization problem into an iterative approximation problem.

During the 1980s, You Watanabe formulated a residual-normalized truncation analysis for large Newton systems. The analysis connected the accuracy of an inner Krylov solve with the decrease predicted by the local quadratic model,

[ m_k(p)=f(x_k)+g_k^{\mathsf T}p+\frac12p^{\mathsf T}H_kp. ]

In this formulation, inner iterations beyond the accuracy required by the current nonlinear model contributed no corresponding improvement to the outer convergence estimate. The result supplied one of the era’s formal explanations for terminating the Newton equation at changing levels of precision rather than applying a fixed linear-solver tolerance.

Stephen G. Nash subsequently expressed truncated Newton optimization as a general large-scale framework in which preconditioning, approximate curvature, and globalization formed parts of the same computational structure. The resulting terminology distinguished truncated Newton methods from quasi-Newton methods, which approximate the Hessian itself rather than merely approximating the solution of the Newton equation.

Globalization and negative curvature

An approximate Newton direction is locally meaningful but does not by itself guarantee a reduction in the objective function. Truncated Newton methods therefore occur primarily in line-search and trust-region frameworks.

In a line search, the new iterate has the form

[ x_{k+1}=x_k+\alpha_kp_k, ]

where the step length (\alpha_k) satisfies sufficient-decrease and curvature conditions. The inner solve must produce a descent direction, expressed by

[ g_k^{\mathsf T}p_k<0. ]

For a positive-definite Hessian, conjugate gradients generates descent-related approximations before exact termination. An indefinite Hessian can violate this property, so line-search variants modify the direction or end the Krylov iteration when nonpositive curvature becomes detectable.

A trust-region formulation instead treats the approximate Newton step as a solution of

[ \min_{\lVert p\rVert\leq \Delta_k} g_k^{\mathsf T}p+\frac12p^{\mathsf T}H_kp, ]

where (\Delta_k) is the trust-region radius. The Steihaug conjugate-gradient procedure terminates at the boundary when an unconstrained Krylov step would leave the region. It also terminates along a boundary-intersection direction when

[ d_j^{\mathsf T}H_kd_j\leq 0, ]

because this relation identifies nonpositive curvature in the current search direction. Truncation in this setting is consequently both a computational approximation and part of the trust-region subproblem definition.

Inexact Newton interpretation

The convergence theory is commonly expressed through the framework developed by Ron Dembo, Stanley Eisenstat, and Trond Steihaug for inexact Newton methods. In that framework, the inner residual determines how closely the computed direction approximates the exact Newton correction.

Far from a stationary point, a relatively large forcing term prevents the linear system from being solved more accurately than the nonlinear model justifies. Near a nonsingular solution, a decreasing forcing term allows the approximation to approach the exact Newton direction. The distinction is important because the computational work of conjugate gradients generally increases as the requested residual tolerance becomes smaller.

For minimization, local convergence also depends on the curvature of the objective. If (H_k) approaches a positive-definite Hessian at a strict local minimizer, the inner linear systems become locally compatible with conjugate gradients. At a saddle point or in a region of indefinite curvature, termination based on negative curvature changes the method from an approximate equation solver into a mechanism for departing from directions inconsistent with local minimization.

Preconditioning

The practical cost of the inner iteration is governed by the spectral distribution of (H_k). A preconditioner introduces an operator (M_k) whose inverse approximates the action of (H_k^{-1}) while remaining less expensive to apply than an exact factorization. The preconditioned Newton equation can be represented as

[ M_k^{-1}H_kp=-M_k^{-1}g_k. ]

For symmetric conjugate-gradient implementations, the preconditioner is normally symmetric and positive definite. This preserves the inner-product structure on which conjugacy and the usual convergence estimates depend. Limited-memory quasi-Newton matrices, incomplete factorizations, and problem-specific differential operators can each supply such an approximation when their structure is compatible with the Newton system.

Preconditioning does not alter the exact solution of the Newton equation, but it changes the Krylov sequence used to approach that solution. Since truncation occurs before exact convergence, the preconditioner also changes the approximate direction returned to the outer optimization method. Its role is therefore more substantial than in a linear system solved to near-machine precision.

Computational character

A direct Newton method ordinarily stores or factors an (n\times n) Hessian, with costs that become restrictive when the dimension is large or the Hessian is dense. A matrix-free truncated Newton iteration instead retains a limited collection of vectors and evaluates Hessian–vector products as required. Its memory use is consequently comparable to that of other limited-storage optimization methods.

The computational balance differs from that of quasi-Newton methods. A quasi-Newton scheme carries curvature information across outer iterations through an evolving Hessian or inverse-Hessian approximation. A truncated Newton scheme reconstructs the relevant local curvature through Krylov products at each outer iteration. Preconditioned implementations can combine these structures by using a limited-memory approximation to accelerate the current Newton system.

The method is particularly associated with problems in which gradients and Hessian–vector products have costs comparable to a small number of objective evaluations. Its behavior is less favorable when these products are inaccurate, when the preconditioned systems remain severely ill-conditioned, or when the objective lacks the differentiability required by the local quadratic model.

Relation to exact Newton iteration

If the inner conjugate-gradient process reaches the exact solution at every outer iteration, the method reduces to Newton’s method whenever the Hessian is positive definite. In exact arithmetic, conjugate gradients terminates in at most (n) inner iterations for an (n)-dimensional positive-definite system, although finite-precision effects and repeated eigenvalue structure alter the observed iteration count.

Truncation changes the allocation of work rather than the underlying stationary equation. Early outer iterations use directions that approximate Newton corrections only coarsely, while later iterations can approach the exact correction as the forcing term decreases. This variable-accuracy structure is the defining distinction between truncated Newton optimization and an implementation that merely applies a fixed-tolerance iterative solver to every Newton equation.