Minimization - General Process

Contents

Introduction

An important method for exploring the potential energy surface is to find configurations that are stable points on the surface. This means finding a point in the configuration space where the net force on each atom vanishes. By simply minimizing the energy, stable conformations can be identified. Perhaps more important, the addition of external forces to the molecule in the form of restraints allows for the development of a wide range of modeling strategies using minimization strategies as the foundation for answering specific questions. For example, the question "How much energy is required for one molecule to adopt the shape of another?" can be answered by forcing specific atoms to overlap atoms of a template structure during an energy minimization.

Minimization of a molecule is done in two steps. First, an equation describing the energy of the system as a function of its coordinates must be defined and evaluated for a given conformation. Target functions may be constructed that include external restraining terms to bias the minimization, in addition to the energy terms. Next, the conformation is adjusted to lower the value of the target function. A minimum may be found after one adjustment or may require many thousands of iterations, depending on the nature of the algorithm, the form of the target function, and the size of the molecule. The efficiency of the minimization is therefore judged by both the time needed to evaluate the target function and the number of structural adjustments (iterations) needed to converge on the minimum. Appropriate target functions for molecular design strategies are described under Forcefields and Constraints and Restraints. First, the principles, advantages, and disadvantages of the most commonly used minimization algorithms are discussed.

Specific Minimization Example

To introduce the various minimization algorithms, the application of each algorithm to the minimization of a pure quadratic function in two dimensions is discussed. Although the energy surface is most certainly anharmonic in regions away from the minimum, it may be considered to be locally harmonic at the minimum.

The target function used here is an elliptical surface in two dimensions described by Eq. 4-1:

Eq. 4-1:
This simple function illustrates the properties of the minimization algorithms and captures the mathematical essence of the formulations. Every minimization begins with some equation analogous to Eq. 4-1. In addition to an equation defining the energy surface, a starting set of coordinates--an initial guess--for (x,y) must be provided. Figure 4-1 is a contour plot of the energy E in the (x,y) plane. Each ellipse is spaced two energy units apart and represents a locus of points having the same energy. (This is analogous to a contoured topographical map.)

Of course, the minimum of this simple function is trivial and can be deduced by inspection to be (0,0).

Given a target function that defines the energy surface (such as in Figure 4-1) and an initial starting point, a minimizer must determine both the direction towards a minimum and the distance to the minimum in that direction. A good initial direction is simply the slope or derivatives of the function at the current point. The derivatives of Eq. 4-1 are a two-dimensional vector:

Eq. 4-2:
Here, the derivatives are proportional to the coordinates, so that, the further you are from the minimum, the larger the derivatives.

The derivatives, however, merely point downhill and not necessarily towards the minimum (see Figure 4-2). Thus, as you move in the direction of the initial derivatives, the new derivatives change and point in yet a new direction. In order to improve the efficiency, the more sophisticated algorithms such as conjugate gradients and Newton-Raphson use information on how the derivatives change, to determine the direction.

Line Search

Before detailing the different algorithms, the concept of a line search is introduced. Line searches are an implicit component of most minimizers.

Minimizers usually have two major components. The more generic part is the so-called line search, which actually changes the coordinates to a new lower-energy structure. As an illustration, consider Figure 4-2, in which the gradient direction from an arbitrary starting point has been superimposed on our elliptic function. The starting point (x0, y0) is defined as point a.

In simple terms, a line search amounts to a one-dimensional minimization along a direction vector determined at each iteration. For the path shown in Figure 4-2, it would be along derivative vector (2x,10y), and the one-dimensional surface can be expressed parametrically in terms of coordinate (see also Figure 4-3):

Eq. 4-3:
where (x', y') are coordinates along the line away from the current point (x0, y0) in the direction of the derivative at (x0, y0).

If the energy of these new points is calculated and plotted as a function of , the curve in Figure 4-3 is obtained.

The minimum along (c) coincides with the point at which the line is tangential to the energy contour. Because the maximum derivative's direction is perpendicular to the search line at this point, each line search is orthogonal to the previous one. This is an important property of line searches, which is also included in the discussion of the conjugate gradients algorithm.

Line searches do not depend on the algorithm that generated the direction vector. The general strategy is to simply bracket the one-dimensional minimum between two points higher in energy, for example points b and d in Figure 4-3. Then, by a set of successive iterations, the actual minimum is approached (e.g., starting at point a, the first step might lead to b, then the direction might reverse to lead to d and finally to c). Extensive line searches are attractive because they extract all the energy from one direction before moving on to the next. Also, the fact that the new derivatives are always perpendicular to the previous directions produces an efficient path to the minimum for approximately quadratic surfaces. In practice, however, line searches are costly in terms of the number of function evaluations that must be performed. The energy must be evaluated at 3-10 points to precisely locate the one-dimensional minimum, and thus extensive line searches are inefficient.

Main access page Theory/Methodology access.

Minimization access Minimization Algorithms

Copyright Biosym/MSI