Truncated-Newton method

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. 

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... 

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. 

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]). 

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. 

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 ... 

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. 

Schlick and Overton have given a truncated Newton method for the... 

Minimization and vibrational analysis are useful for the determination of force field parameters, system preparation, and the study of many problems of biological interest. A new optimizer based on a truncated Newton method (TNPACK) that is effective for large molecules has been added to CHARMM. All minimizers, excluding TNPACK, support the use of holonomic constraints on selected bonds and angles (SHAKE). Vibrational analysis has been extended via addition of the MOLVIB module (K. Kuczera and J. Wiorkiewicz-Kuczera, unpublished), which allows for the determination of potential energy distributions and the analysis of lattice modes in combination with the CRYSTAL facility. Minimizations may also be performed in the presence of a variety of structural constraints. This allows for atomic positions, internal coordinates, interatomic distances, etc. to be fixed or constrained to specified values. Such constraint methods may be used in molecular dynamics simulations. 

In most molecular mechanics packages, the second derivatives are programmed, though sparsity (when relevant) is not often exploited in the storage techniques for large molecular systems. The optimizer should utilize some of this second-derivative information to make the algorithm more efficient. Truncated Newton methods, for example, are designed with this philosophy. 

The popular methods that fit the descent framework outlined in Sections (4.1) and (4.2) require gradient information. In addition, the truncated-Newton method may require more input to be effective, such as partial, but explicit, second-derivative information. The methods described in this section render steepest descent (SD) obsolete as a general method. In SD, the descent direction is defined as pt = —g(x ) at each step. Only if the energy and gradient at xq are very high, SD may be useful for a few iterations, before a better minimizer is applied. 

Still, the linear and nonlinear CG methods play important theoretical roles in the numerical analysis literature as well as practical roles in many numerical techniques see the recent research monograph of Adams and Nazareth for a modem perspective. The linear CG method, in particular, proves ideal for solving the linear subproblem in the truncated Newton method for minimization (discussed next), especially with convergence-accelerating techniques known as preconditioning. 

---