Conjugate gradient descent

IlyperChem supplies three types of optimi/ers or algorithms steepest descent, conjugate gradient (Fletcher-Reeves and Polak-Ribiere), and block diagonal (Newton-Raph son). 

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. 

Tafe/e 5.1 A comparison of the steepest descents and conjugate gradients methods for an initial refinement and a stringent minimisation. 

This study shows that the steepest descent method can actually be superior to conjugate gradients when the starting structure is some way from the minimum. However, conjugate gradients is much better once the initial strain has been removed. 

The advantage of a conjugate gradient minimizer is that it uses the minimization history to calculate the search direction, and converges faster than the steepest descent technique. It also contains a scaling factor, b, for determining step size. This makes the step sizes optimal when compared to the steepest descent technique. 

Example Compare the steps of a conjugate gradient minimization with the steepest descent method. Amolecular 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 minimum(E) because the optimizer remembers the penultimate step. 

Techniques used to find global and local energy minima include sequential simplex, steepest descents, conjugate gradient and variants (BFGS), and the Newton and modified Newton methods (Newton-Raphson). 

The steepest descent method is quite old and utilizes the intuitive concept of moving in the direction where the objective function changes the most. However, it is clearly not as efficient as the other three. Conjugate gradient utilizes only first-derivative information, as does steepest descent, but generates improved search directions. Newton s method requires second derivative information but is veiy efficient, while quasi-Newton retains most of the benefits of Newton s method but utilizes only first derivative information. All of these techniques are also used with constrained optimization. 

Figure 5 A comparison of steepest descent (SD) minimization and conjugated gradients (CG) minimization of the same protein.

The Polak-Ribiere prescription is usually preferred in practice. Conjugate gradient methods have much better convergence characteristics than the steepest descent, but they are again only able to locate minima. They do require slightly more storage than the steepest descent, since the previous gradient also must be saved. 

We first examine the classic steepest descent method of using the gradient and then examine a conjugate gradient method. 

The basic difficulty with the steepest descent method is that it is too sensitive to the scaling of/(x), so that convergence is very slow and what amounts to oscillation in the x space can easily occur. For these reasons steepest descent or ascent is not a very effective optimization technique. Fortunately, conjugate gradient methods are much faster and more accurate. 

---