Minimization methods gradient based

The problem of local minima in function minimization or optimization problems has given rise to the development of a variety of algorithms which are able to seek global minima. Traditional gradient based optimizers proceed by the selection of fruitful search directions and subsequent numerical one-dimensional optimization along these paths. Such methods are therefore inherently prone to the discovery of local minima in the vicinity of their starting point, as illustrated in Fig. 5.4(b). This property is in fact desirable in... 

Figure 5.4 (a) Gradient based minimization methods proceed downhill from a starting point, S, towards the nearest minimum, M. In 4(b) this behaviour can only find the nearer local minimum, LM, and not the deeper minimum, M. 

As noted in the introduction, energy-only methods are generally much less efficient than gradient-based techniques. The simplex method [9] (not identical with the similarly named method used in linear programming) was used quite widely before the introduction of analytical energy gradients. The intuitively most obvious method is a sequential optimization of the variables (sequential univariate search). As the optimization of one variable affects the minimum of the others, the whole cycle has to be repeated after all variables have been optimized. A one-dimensional minimization is usually carried out by finding the... 

As a rule, independent data points are required to solve a harmonic function with N variables numerically. Because a gradient is a vector N long, the best one can hope for in a gradient-based minimizer is to converge in N steps. However, if one can exploit second-derivative information, an optimization could converge in one step, because each second derivative is an V x V matrix. This is the principle behind the variable metric optimization algorithms such as Newton-Raphson method. 

The method of Ishida et al [84] includes a minimization in the direction in which the path curves, i.e. along (g/ g -g / gj), where g and g are the gradient at the begiiming and the end of an Euler step. This teclmique, called the stabilized Euler method, perfomis much better than the simple Euler method but may become numerically unstable for very small steps. Several other methods, based on higher-order integrators for differential equations, have been proposed [85, 86]. 

---