Optimization techniques conjugate gradient methods

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. 

Unconstrained optimization (nonlinear programming), 2546-2553 classictil methods, 2546-2547 conjugate gradient methods, 2552-2553 golden section method, 2547-2549 line search techniques for, 2547 multidimensional search techniques for, 2549-2552... 

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 Optimization of the objective function in Modeller. Optimization of the objective function (curve) starts with a random or distorted model structure. The iteration number is indicated below each sample structure. The first approximately 2000 iterations coiTespond to the variable target function method [82] relying on the conjugate gradients technique. This approach first satisfies sequentially local restraints, then slowly introduces longer range restraints until the complete objective function IS optimized. In the remaining 4750 iterations, molecular dynamics with simulated annealing is used to refine the model [83]. CPU time needed to generate one model is about 2 mm for a 250 residue protein on a medium-sized workstation.

Undoubtedly more effective conjugate-gradient techniques would be of most use in quantum chemistry, perhaps some methods tailored to suit particular functional forms common in the field, but this area of research seems unlikely to be developed further by workers principally interested in optimization and is perhaps a suitable field of endeavour for quantum chemists. 

Direct minimization techniques. The variational principle indicates that we want to minimize the energy as a function of the MO coefficients or the corresponding density matrix elements, as given by eq. (3.54). In this formulation, the problem is no different from other types of non-linear optimizations, and the same types of technique, such as steepest descent, conjugated gradient or Newton-Raphson methods can be used (see Chapter 12 for details). 

A number of optimization techniques can be directly applied to QP, such as Newton method, conjugate gradient, and primal dual interior-point method. But in fact, those methods are very hard to use, so they are not widely used in SVM. 

---