A New Stochastic/Perturbation Method for Large-Scale Global Optimization and its Application to Water Cluster Problems

We describe a class of new global optimization methods that has been designed to solve large, partially separable problems. The methods have been motivated by the consideration of problems from molecular chemistry, but should be applicable to other partially separable problems as well. They combine a first, stochastic phase that identifies an initial set of local minimizers, with a second, more deterministic phase that moves from low to even lower local minimizers and that accounts for most of the computational cost of the methods. Both phases make critical use of portions that vary only a small subset of the variables at once. Another important new feature of the methods is an expansion step that makes it easier to find new and structurally different local minimizers from current low minimizers. We give the results of the initial application of these methods to the problem of finding the minimum energy configuration of clusters of water molecules with up to 21 molecules (189 variables). These runs have led to improved minimizers, and interesting structures from the chemistry perspective.