The iterative calculation of a Newton direction or related quadratic-model step is stopped according to a rule.

Does it require storing the Hessian?

Not necessarily. Suitable implementations need only its products with vectors, plus any information required by preconditioning.

Does it preserve Newton's fast convergence?

Appropriate accuracy schedules and regularity assumptions can support fast local convergence, but an arbitrary fixed truncation rule does not guarantee the same rate as exact Newton.

AI Glossary / Mathematics and optimization / Advanced

Truncated Newton method

Definition

A truncated Newton method approximately solves the Newton equations inside each optimization iteration, stopping the inner solve before full accuracy when an appropriate criterion is met. It aims to obtain useful curvature-informed steps without paying for an exact linear-system solution every time. This can be valuable for problems with many variables.

What it means

Newton's method uses a gradient and Hessian to build a local quadratic model. Its step p ideally solves Hp=−g, where g is the current gradient and H is the Hessian. Solving that system exactly can be expensive and may be unnecessary when the model is only locally accurate.

Truncation controls the work spent on this inner calculation. The outer optimization then assesses or safeguards the resulting step, often through a line search or trust-region framework. The term does not mean rounding decision variables or cutting off the objective's decimal digits.

How it works

At the current point, obtain the gradient and a way to apply the Hessian to vectors. An iterative linear solver, commonly a conjugate-gradient-based procedure in appropriate settings, builds an approximate Newton direction.

One stopping rule requires the residual norm ‖Hp+g‖ to be no more than η‖g‖, where 0<η<1 is a chosen forcing tolerance. Tolerances can change across outer iterations so early steps avoid oversolving while later steps become more accurate.

Hessian-vector products can avoid storing a dense Hessian, but not every truncated Newton implementation is necessarily matrix-free. Preconditioning can improve inner convergence. Nonpositive curvature, trust-region boundaries, and numerical difficulties require safeguards. A small linear-system residual alone does not establish that the proposed step improves a nonconvex objective or that the final point is globally optimal.

Three practical examples

1. Large-scale model fitting: use curvature information when a dense Hessian factorization would be costly but Hessian-vector products are practical.

2. Simulation calibration: balance the cost of solving each local quadratic model against the progress made on the original nonlinear objective.

3. Numerical research: compare inner stopping tolerances and preconditioners under an equal computational budget rather than counting only outer iterations.

Think of it this way

Think of using a local map to choose the next stage of a journey. It may be wasteful to plan that short stage with extreme precision while the map will change after you move.

The analogy concerns computational effort, not careless navigation. The approximate direction still needs a quantitative acceptance rule and safeguards. Near a solution, a more accurate local calculation can become worthwhile because the model and desired destination are better aligned.

Worked example

Consider an original quadratic objective f(x,y)=(x−1)²+4(y−1)², starting at (0,0). The gradient is g=(−2,−8), and H=diag(2,8). The exact Newton direction is (1,1), which reaches the minimum immediately for this quadratic.

Now perform only the first conjugate-gradient step for Hp=−g, starting from p=0. The initial residual and direction are b=(2,8). The step coefficient is α=(bᵀb)/(bᵀHb)=68/520=17/130.

The approximate direction is p=αb=(17/65,68/65). Its Newton-equation residual is Hp+g=(−96/65,24/65). The relative residual norm is 12/65≈0.1846, so a tolerance η=0.2 would permit stopping the inner solve after this step.

Taking the full approximate step gives f=36/65≈0.5538, reduced from the initial value 5 but still above the exact minimum 0. This demonstrates useful progress from an intentionally incomplete inner solve.

For this positive-definite quadratic, the arithmetic is straightforward and independently checkable. It is not a claim that one inner iteration is sufficient for general nonlinear problems or that a line search can always be omitted.

Illustrative case study

Fictional case: Oak Numerical Lab fits a large smooth model. Its initial optimizer spends most of its time solving early Newton systems to a very tight tolerance, even though subsequent outer steps substantially change the local curvature.

The team compares adaptive inner tolerances with its original setting, recording objective values, gradient norms, Hessian-vector products, and elapsed time. It checks the final accuracy separately from intermediate progress. The scenario illustrates what to measure, without inventing a speedup or claiming that looser solves always improve performance.

Common misconceptions and mistakes

Truncated Newton is not quasi-Newton by definition. Quasi-Newton methods update curvature approximations from previous steps, whereas truncation refers to an incomplete inner solve; implementations can combine ideas, but the concepts differ.

Hessian-free does not mean curvature-free. A matrix-free method can still use Hessian-vector products. Likewise, fewer outer iterations do not necessarily mean less total work if each requires many expensive inner operations.

Do not run ordinary positive-definite conjugate gradients uncritically on an indefinite Hessian. Negative-curvature detection or other safeguards are part of robust variants.

Business use

The practical benefit is a controllable trade-off between step quality and computation. It is most relevant when accurate derivatives or useful Hessian-vector products are available and problem size makes direct factorization unattractive.

Evaluate total derivative work, memory, robustness, and final stationarity rather than only iteration counts. Record forcing tolerances, preconditioners, and outer step safeguards. If gradient or curvature evaluations are noisy or approximate, ensure inner accuracy targets are meaningful relative to that uncertainty; solving an inaccurate local system extremely precisely may add little value.

Check your understanding

Why can the worked inner solve stop at p=(17/65,68/65) with η=0.2?

Answer: Its residual is only about 0.1846 times the gradient norm, below the chosen 0.2 threshold. The criterion permits an approximate direction; it does not assert that the exact Newton equations have been solved.

Related terms

Conjugate gradient
Preconditioning
Trust region
Line search
Newton's method
Hessian-vector product
inexact Newton method
forcing tolerance
negative curvature

Learn next

Verify the worked residual and objective reduction by hand, then compare with the exact Newton direction. Study conjugate gradients for positive-definite systems before adding negative-curvature safeguards. Finally examine how inner tolerances interact with line-search or trust-region decisions on a nonlinear objective.

Sources

Primary sources: NEOS Guide, “Truncated Newton Methods”, https://neos-guide.org/guide/algorithms/truncated-newton/ ; COPASI's method description, https://copasi.org/Support/User_Manual/Methods/Optimization_Methods/Truncated_Newton/ . The incomplete-solve description and relative-residual stopping rule were consulted. The quadratic and first inner iteration are original analytic calculations, not executed optimizer output.

Previous: True positive rate Next: Truncated normal distribution