Semi-Global Optimization

A fundamental computational problem in molecular modeling is finding the global minimum on a complex free energy surface, generally with a large number of local minima. Our goal is to develop and test search methods that move on a smooth surface spanned by these local minima, rather than on the rugged energy surface itself. The Convex Global Underestimator (CGU), developed by Rosen, Phillips and Dill fits a quadratic global underestimating function to a selected set of local minima, and finds the global minimum of the underestimator. This serves as the starting point of a new local minimization, and the updated set of local minima is used as the basis for another quadratic underestimation step in an iterative algorithm. Since using a canonical quadratic underestimator is a restriction, we currently work on the generalizations of CGU, improving its performance for a variety of functions.

An approach we have developed is the Semi-Global Simplex (SGS) algorithm, a straightforward extension of the classical nonlinear simplex method. Although SGS does not guarantee finding the global minimum, it affords a much more thorough exploration of the local minima than any traditional minimization method[1]. The basic idea of SGS is to perform a local minimization in each step of the simplex method and thus, similarly to the CGU method, the search is carried out on a surface spanned by local minima. While CGU delivers better success rates than SGS in simple problems, SGS performs better as the complexity of the function increases, and good approximation by canonical quadratic functions becomes restricted to smaller regions.


References