Steepest descents

The Steepest Descent method is the simplest optimization algorithm. The initial energy [T o] = (co), which depends on the plane wave expansion coefficients c (see O Eq. 7.67), is lowered by altering c in the direction of the negative gradient. 

Molecular Dynamics Simulation From Ab Initio to Coarse Grained  

HyperChem supplies three types of optimizers or algorithms steepest descent, conjugate gradient (Hetcher-Reeves and Polak-Ribiere), and block diagonal (Newton-Raphson). 

The steepest descent method is a first order minimizer. It uses the first derivative of the potential energy with respect to the Cartesian coordinates. The method moves down the steepest slope of the interatomic forces on the potential energy surface. The descent is accomplished by adding an increment to the coordinates in the direction of the negative gradient of the potential energy, or the force. 

The steepest descent method rapidly alleviates large forces on atoms. This is especially useful for eliminating the large non-bonded interactions often found in initial structures. Each step in 

The gradient vector g points in the direction where the function increases most, i.e. the function value can always be lowered by stepping in the opposite direction. In the Steepest Descent (SD) method, a series of function evaluations are performed in the negative gradient direction, i.e. along a search direction defined as d = -g. Once the function starts to increase, an approximate minimum may be determined by interpolation between the calculated points. At this interpolated point, a new gradient is calculated and used for the next line search. 

The steepest descent algorithm is sure-fire. If the line minimization is carried out sufficiently accurately, it will always lower the function value, and is therefore guaranteed to approach a minimum. It has, however, two main problems. Two subsequent line searches are necessarily perpendicular to each other if there was a gradient component along the previous search direction, the energy could be further lowered in this direction. The steepest descent algorithm therefore has a tendency for each line search to partly spoil the function lowering obtained by the previous search. The steepest 

Furthermore, as the minimum is approached, the rate of convergence slows down. The steepest descent will actually never reach the minimum, it will crawl towards it at an ever decreasing speed. 

In the one-dimensional search methods there are two principle variations some methods employ only first derivatives of the given function (the gradient methods), whereas others (Newton s method and its variants) require explicit knowledge of the second derivatives. The methods in this last category have so far found very limited use in quantum chemistry, so that we shall refer to them only briefly at the end of this section, and concentrate on the gradient methods. The oldest of these is the method of steepest descent. 

Steepest Descent. The algorithm for the steepest descent is really very simple  

The reason for the name steepest descent is obvious from this algorithm 

The first derivative of an energy function is computed to find the minimum. The energy is computed for the given confirmation and then again after one of the atoms is moved in small increments in one of the directions of the coordinate system. This process is followed for all the atoms and finally whole molecule is moved to a position downhill on the potential energy surface. The process is repeated until the desired threshold condition is fulfilled. The process is more suitable for the optimization far away from the minimum as a rough and fast method to reach closer to the minimum. 

Tlie function to be optimized, and its derivative(s), are calculated with a finite precision, which depends on the computational implementation. A stationary point can therefore not be located exactly, the gradient can only be reduced to a certain value. Below this value the numerical inaccuracies due to the finite precision will swamp the true functional behaviour. In practice the optimization is considered converged if the gradient is reduced below a suitable cut-off value. It should be noted that this in some cases may lead to problems, as a function with a very flat surface may meet the criteria without containing a stationary point. 

There are three classes of commonly used optimization methods for finding minima, each with its advantages and disadvantages. 

An accurate line search will require several function evaluations along each search direction. Often the minimization along the line is only carried out fairly crudely, or a 

By nature the steepest descent method can only locate function minima. The 

Its main use is to quickly relax a poor starting point, before some of the more advanced algorithms take over, or as a backup algorithm if the more sophisticated methods are unable to lower the function value. 

---

It should be noted that in the cases where y"j[,q ) > 0, the centroid variable becomes irrelevant to the quantum activated dynamics as defined by (A3.8.Id) and the instanton approach [37] to evaluate based on the steepest descent approximation to the path integral becomes the approach one may take. Alternatively, one may seek a more generalized saddle point coordinate about which to evaluate A3.8.14. This approach has also been used to provide a unified solution for the thennal rate constant in systems influenced by non-adiabatic effects, i.e. to bridge the adiabatic and non-adiabatic (Golden Rule) limits of such reactions. 

If there is no approximate Hessian available, then the unit matrix is frequently used, i.e., a step is made along the gradient. This is the steepest descent method. The unit matrix is arbitrary and has no invariance properties, and thus the... 

Figure B3.5.1. Contour line representation of a quadratic surface and part of a steepest descent path zigzagging toward the minimum.

An alternative, and closely related, approach is the augmented Hessian method [25]. The basic idea is to interpolate between the steepest descent method far from the minimum, and the Newton-Raphson method close to the minimum. This is done by adding to the Hessian a constant shift matrix which depends on the magnitude of the gradient. Far from the solution the gradient is large and, consequently, so is the shift d. One... 

Aq becomes asymptotically a g/ g, i.e., the steepest descent fomuila with a step length 1/a. The augmented Hessian method is closely related to eigenvector (mode) following, discussed in section B3.5.5.2. The main difference between rational fiinction and tmst radius optimizations is that, in the latter, the level shift is applied only if the calculated step exceeds a threshold, while in the fonuer it is imposed smoothly and is automatically reduced to zero as convergence is approached. 

The reaction path is defined by Fukui [83] as the line q(.s) leading down from a transition state along the steepest descent direction... 

As shown by Valtazanos and Ruedenberg [93], steepest descent paths (e.g., the Fiikui intrinsic reaction coordinate)... 

Page M, Doubleday C and Mclver J W Jr 1990 Following steepest descent reaction paths. The use of higher energy derivatives with ab initio electronic structure methods J. Chem. Phys. 93 5634 and references therein... 

Sun J-Q and Ruedenberg K 1993 Quadratic steepest descent on potential energy surfaces. I. Basic formalism and quantitative assessment J. Chem. Phys. 99 5257... 

R. Olender and R. Elber, Yet another look at the steepest descent path , J. Mol. Struct. Theochem and the proceeding of the WATOC symposium, 398-399, 63-72 (1997)... 

A con jugate gradicri I method differs from the steepest descent technique by using both the current gradient and the previous search direction to drive the rn in im i/ation. , A conjugate gradient method is a first order in in im i/er. 

The advan tage ol a conjugate gradien t m iniim/er is that it uses th e minim i/ation history to calculate the search direction, and converges t asLer Lhan the steepest descent technique. It also contains a scaling factor, b, for determining step si/e. This makes the step si/es optimal when compared to the steepest descent lechniciue. 

Example Com pare the steps of a conjugate gradien t min im i/ation with the steepest descent method.. A molecular system can reach a potential minimum after the second step if the first step proceeds from, A to B. If the first step is too large, placing the system at D, the second step still places the system near the tninimum(K ) because the optim i/,er remembers the penultimate step. 

Steepest Descent is the simplest method of optimization. The direction of steepest descen t. g, is just th e n egative of the gradien t vector ... 

HyperChein uses the steepest descent by steps method. New points are found by ... 

The principal difficulty with steepest descent is that the successive direction s of search, g,., . .. arc ri ot conjugate direction s. 

Another difference from steepest descent is that a one-diinen-sional minimization is performed in each search direction. Aline mmimi/ation is made along a direction h until a minlmnni energy is found at anew point i-i-l then the search direction is updated and a search down the new direction h ] is made. This... 

A starting poin t is defined an d th e in itial conjugate direction is chosen to be the steepest descent direction, h[, = g... 

The conjugate direction is reset to the steepest descent direction every 3N search direction s or cycles, or if the en ergy rises between cycles. 

The gradient at the minimum point obtained from the line search will be perpendicular to the previous direction. Thus, when the line search method is used to locate the minimum along the gradient then the next direction in the steepest descents algorithm will be orthogonal to the previous direction (i.e. gk Sk-i = 0)-... 

---