Truncated Newton Methods

The line-search and trust-region techniques that we have described are suitable if the number of variables is not too large since the cost per iteration is of order . Codes for problems with a large number of variables tend to use iterative techniques for obtaining a direction in a line-search method or a step in a trust-region method. These techniques are usually called truncated Newton methods because the iterative technique is stopped (truncated) as soon as a termination criterion is satisfied.

For example, the codes in BTN , TN , TNPACK , and VE08 use a line-search method in which the direction satisfies

for some .

The LANCELOT codes use a similar idea in the context of trust-region methods. Conjugate gradient algorithms mesh well with truncated Newton methods because of their desirable numerical properties. Preconditioning is necessary in order to improve the efficiency and reliability of the conjugate gradient method; effective preconditioners include those based on the incomplete Cholesky factorization and symmetric successive overrelaxation.

Up To:

Unconstrained Optimization.

[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]

Updated 28 March 1996