Clustering methods for large scale geometrical global optimization

In this paper we wish to show that for some specific problem classes, it is possible to design Global Optimization algorithms which mimic the behavior of existing procedures and obtain the same quality but at a fraction of their computational cost. The way we achieved this is through the application of clustering methods designed to identify the regions of attraction of good local minima. Ideally, if we were able to identify the shape of these regions of attraction, a single local search starting from each of them would lead to the global minimum. This idea had been a winning one in the 80’s, and later abandoned when large dimensional global optimization problems were used to test global optimization algorithms. In this paper we show that by using the idea of clustering in a feature space of much smaller dimension than the original one, very significant speed ups can be obtained. We present the general idea and apply it to two of the most widely studied families of hard, large scale, global optimization problems: the optimization of the potential energy of atomic clusters, and the problem of packing a set of identical spheres of largest radius in the unit hypercube. In this latter problem we could even improve some existing putative optima, thus proving that the proposed method is not only very efficient but also effective in exploring the feasible space.