Truncated Newton

Truncated Newton methods were introduced in the early 1980s111-114 and have been gaining popularity ever since.82-109 110 115-123 Their basis is the following simple observation. An exact solution of the Newton equation at every step is unnecessary and computationally wasteful in the framework of a basic descent method. That is, an exact Newton search direction is unwarranted when the objective function is not well approximated by a convex quadratic and/or the initial point is distant from a solution. Any descent direction will suffice in that case. As a solution to the minimization problem is approached, the quadratic approximation may become more accurate, and more effort in solution of the Newton equation may be warranted. 

the approximate Newton search direction in TN methods is obtained by allowing a nonzero residual norm rk = rj = H p + gA at each step. The size of this residual is monitored systematically according to the progress made. This formulation leads to a doubly nested iteration structure for every outer Newton iteration k (associated with xk) there corresponds an inner loop for pk p p 1,. . . .  

As the linear PCG method is one of the most powerful and computationally economical iterative methods for solving large positive-definite linear systems, it is the most suitable choice here for the inner loop. 

The performance and large-scale feasibility of a TN algorithm depend on the precise formulation of a truncation criterion and implementation of the inner PCG loop. The PCG process can be terminated when either one of the following conditions is satisfied (1) the residual rk is sufficiently small, (2) the quadratic model qk p ) as defined in Eq. [35] is sufficiently reduced, or (3) a direction of negative curvature d is encountered (i.e., 0). A negative 

An effective residual test (RT)113 checks at each inner iteration whether the relative residual fk is sufficiently small  

---

T. Schlick and A. Fogelson, TNPACK - A truncated Newton minimization package for large scale problems, ACM Trans. Math. Softw. 18 (1992), 46-70 71-111. 

T. Schlick and M. L. Overton. A powerful truncated Newton method for potential energy functions. J. Comp. Chem., 8 1025-1039, 1987. 

P. Derreumaux, G. Zhang, B. Brooks, and T. Schlick. A truncated-Newton method adapted for CHARMM and biomolecular applications. J. Comp. Chem., 15 532-552, 1994. 

D. Xie and T. Schlick. Efficient implementation of the truncated Newton method for large-scale chemistry applications. SIAM J. Opt, 1997. In Press. 

Watanabe, M., Karplus, M. Dynamics of Molecules with Internal Degrees of Freedom by Multiple Time-Step Methods. J. Chem. Phys. 99 (1995) 8063-8074 Figueirido, F., Levy, R. M., Zhou, R., Berne, B. J. Large Scale Simulation of Macromolecules in Solution Combining the Periodic Fast Multiple Method with Multiple Time Step Integrators. J. Chem. Phys. 106 (1997) 9835-9849 Derreumaux, P., Zhang, G., Schlick, T, Brooks, B.R. A Truncated Newton Minimizer Adapted for CHARMM and Biomolecular Applications. J. Comp. Chem. 15 (1994) 532-555... 

Xie D, Tropsha A, Schlick T. An efficient projection protocol for chemical databases singular value decomposition combined with truncated-newton minimization. / Chem Inf Comput Sci 2000 40 167-77. 

Although line searches are typically easier to program, trust region methods may be effective when the procedure for determining the search direction p is not necessarily one of descent. This may be the case for methods that use finite-difference approximations to the Hessian in the procedure for specifying p (discussed in later sections). As we shall see later, in BFGS quasi-Newton or truncated Newton methods line searches may be preferable because descent directions are guaranteed. 

Two specific classes are emerging as the most powerful techniques for large-scale applications limited-memory quasi-Newton (LMQN) and truncated Newton methods. LMQN methods attempt to combine the modest storage and computational requirements of CG methods with the superlinear convergence properties of standard (i.e., full memory) QN methods. Similarly, TN... 

Algorithm [A5] Truncated Newton (Inner Loop of Outer Step k)... 

Truncated Newton methods can be competitive only with preconditioning. Thus, the operation count for obtaining p in TN reflects IT inner PCG iterations per Newton step. Each such inner iteration involves the following operations an Hd multiplication (an, for an additional gradient evaluation in this finite-difference approximation [58]) calculation of the PCG vectors and scalars (7 , Algorithm [A4]) and numerical solution of Mz = r by forward and backward substitution (0(1), see [61]). 

Figure 14 Minimization paths by different methods for the two-dimensional Rosen-brock function f(xx,x2) = (1 — x,)2 + 100(x2 - x,2)2 (a) truncated Newton, (b) conjugate gradient, (c) BFGS quasi-Newton, (d) limited-memory BFGS, (e) steepest descent, first 150 iterations. See program output in Figure 15.

L. C. W. Dixon, SIAM J. Opt., 1,475 (1991). On the Impact of Automatic Differentiation on the Relative Performance of Parallel Truncated Newton and Variable Metric Algorithms. 

T. Schlick and M. Overton, J. Comput. Chem., 8, 1025 (1987). A Powerful Truncated Newton Method for Potential Energy Minimization. 

S. G. Nash and J. Nocedal, SIAM ). Opt., 1 358-372 (1991). A Numerical Study of the Limited Memory BFGS Method and the Truncated-Newton Method for Large-Scale Optimization. 

R. S. Dembo and T. Steihaug, Math. Prog., 26, 190 (1983). Truncated-Newton Algorithms for Large-Scale Unconstrained Optimization. 

S. G. Nash, in Numerical Optimization 1984, P. T. Boggs, R. H. Byrd, and R. B. Schnabel, Eds., pp. 119-136, SIAM, Philadelphia, 1985. Solving Nonlinear Programming Problems Using Truncated-Newton Techniques. 

S. G. Nash and A. Sofer, Oper. Res. Lett., 9,219 (1990). Assessing a Search Direction Within a Truncated Newton Method. 

S. G. Nash, SIAM J. Sci. Statist. Comput., 6, 599 (1985). Preconditioning of Truncated-Newton Methods. 

L. Fauci and A. Fogelson, Comm. Pure Appl. Math., in press. Truncated Newton Methods and the Modeling of Immersed Elastic Structures. 

Here the linear system of the Newton equation is solved by yet another inner iteration (e.g. conjugate gradients) until a prespecified tolerance is reached. This tolerance can be chosen adaptively to recapture quadratic local convergence (see Dembo and Steihaug [1]). The iterative approach makes the truncated Newton method especially attractive for large scale problems and it is a much better procedure than the simple rule of thumb Hake Newton if good else gradienf ... 

The subspaces could be spanned by the usual search directions current gradient g xk) Newton step n(xjb), truncated Newton step n xk). Or we can use the iteration history of the solver (which is very cheap) old gradient values, previous iteration steps. And it is possible to use curve approximations, or any other useful information at hand. The choice should be adapted to the problem (size, costs, known behavior, etc.). 

The last subspace is build up by the truncated Newton step and the gradient direction ... 

But now we do a comparison with the truncated Newton method. The results (see Table 2, third row) indicate, that the truncated Newton method is hard to beat, but the subspace approach is much more robust. 

Newton failed on problem 1 in two runs, on problem 3 in one run. Truncated Newton failed on problem 3 in two runs. 

---