CHARMM tutorial: Description of Minimization

Minimization reduces the energy of the system to the lowest possible point, simulating the system's energy as absolute zero.

Minimization algorithms

There are different methods used for calculating the lowest-energy conformation of a given structure. These descriptions here were taken from minimiz.doc, which is one of the standard documentation files included with CHARMM. The SD and ABNR methods are the most commonly utilized and will therefore be used in this tutorial when making minimization input scripts.

Steepest Descent (SD)
The simplest minimization algorithm is steepest descent (SD). In each step of this iterative procedure, the coordinates are adjusted in the negative direction of the gradient. It has one adjustable parameter, the step size, which determines how far to shift the coordinates at each step. The step size is adjusted depending on whether a step results in a lower energy. i.e., if the energy drops, the step size is increased by 20% to accelerate the convergence. If the energy rises, overshooting a minimum, the step size is halved. Steepest descent does not converge in general, but it will rapidly improve a very poor conformation.

Conjugate Gradient Technique (CONJ)
A second method is the conjugate gradient technique (CONJ) which has better convergence characteristics (R. Fletcher & C.M. Reeves, The Computer Journal 7:149 (1964)). The method is iterative and makes use of the previous history of minimization steps as well as the current gradient to determine the next step. It can be shown that the method converges to the minimum energy in N steps for a quadratic energy surface where N is the number of degrees of freedom in the energy. Since several terms in the potential are quadratic, it requires less evaluations of the energy and gradient to achieve the same reduction in energy in comparison to steepest descent. Its main drawback is that with very poor conformations, it is more likely to generate numerical overflows than steepest descent. The algorithm used in CHARMM has a slightly better interpolation scheme and automatic step size selection.

Conjugate Gradient Powell Method Minimizer (POWE)
A third method is the conjugate gradient powell method minimizer (POWE) (A. Brunger). Its efficiency is much improved over the Fletcher and Reeves method. The use of the POWELL minimizer is encouraged whenever ABNR is not possible. The POWELL minimizer has no INBFRQ or IHBFRQ feature. The use of CHARMM loops to mimic this important feature is encouraged. The CHARMM loop facilities allow harmonic constrained minimizations with periodic updates. In case of bad contacts or unlikely conformations the SHAKE method might give an error when the displacements become to large. Using a harmonic constraint setup with periodic updates solves this problem.

Newton-Raphson minimization (NRAP)
A fourth method involves solving the Newton-Raphson minimization equations iteratively (NRAP). This procedure requires the computation of the derivative of the gradient which is a matrix of size O(n2). The procedure here is to find a point where the gradient will be zero (hopefully a minimum in energy) assuming that the potential is quadratic. The Newton-Raphson equations can be solved by a number of means, but the method adopted for CHARMM involves diagonalizing the second derivative matrix and then finding the optimum step size along each eigenvector. When there are one or more negative eigenvalues, a blind application of the equations will find a saddle point in the potential. To overcome this problem, a single additional energy and gradient determination is performed along the eigenvector displacement for each small or negative eigenvalue. From this additional data, the energy function is approximated by a cubic potential and the step size that minimizes this function is adopted. The advantages of this method are that the geometry cannot remain at a saddle point, as sometimes occurs with the previous procedures, and that the procedure converges rapidly when the potential is nearly quadratic (or cubic). The major disadvantage is that this procedure can require excessive storage requirements, O(n2), and computation time, O(n3), for large molecules. Thus we are currently restricted to systems with about 200 atoms or less for this method. IMAGES and SHAKE are currently unavailable with this method.

Adopted Basis Newton-Raphson Method (ABNR)
The fifth method available is an adopted basis Newton-Raphson method (ABNR) (D. J. States). This routine performs energy minimization using a Newton-Raphson algorithm applied to a subspace of the coordinate vector spanned by the displacement coordinates of the last (MINDim) positions. The second derivative matrix is constructed numerically from the change in the gradient vectors, and is inverted by an eigenvector analysis allowing the routine to recognize and avoid saddle points in the energy surface. At each step the residual gradient vector is calculated and used to add a steepest descent step onto the Newton-Raphson step, incorporating new direction into the basis set. This method is the best for most circumstances.

Truncated-Newton Minimization Package (TN)
The sixth method is the truncated-Newton (TN) minimization package TNPACK, developed by T. Schlick and A. Fogelson. TNPACK is based on the preconditioned linear conjugate-gradient technique for solving the Newton equations. The structure of the problem --- sparsity of the Hessian --- is exploited for preconditioning. Thorough experience with the new version of TNPACK in CHARMM has been described in the paper: Journal of Computational Chemistry: 15, 532--552, 1994. Through comparisons among the minimization algorithms available in CHARMM, we find that TNPACK compares favorably to ABNR in terms of CPU time when curvature information is calculated by a finite-difference of gradients (the "NUMEric" option of TNPACK). With the analytic option, TNPACK can converge more rapidly than ABNR for small and medium systems (up to 400 atoms) as well as large molecules that have reasonably good starting conformations; for large systems that are poorly relaxed (i.e., the initial Brookhaven Protein Data Bank structures are poor approximations to the minimum), TNPACK performs similarly to ABNR. SHAKe is currently unavailable with this method.