Clustering methods for large scale geometrical global optimization. (3rd September 2019)

• Record Type: Journal Article
• Authors: Bagattini, Francesco; Schoen, Fabio; Tigli, Luca
• Is Part Of: Optimization methods and software. Volume 34:Number 5(2019)
• Page Start: 1099
• Page End: 1122
• Publication Date: 2019-09-03
• Subjects: Global optimization -- clustering methods -- multi level single linkage -- feature space -- Lennard–Jones clusters -- Morse clusters -- sphere packing; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2019.1582651
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: In this paper we show that for some problem classes it is possible to design Global Optimization algorithms which mimic existing procedures obtaining the same quality at a fraction of their computational cost. We achieved this applying clustering methods to identify regions of attraction of local minima. If we could identify the shape of regions of attraction, a local search starting from each of them would lead to the global minimum. This idea had been a winning one in the 1980s, 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 apply this idea 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 identical spheres of largest radius in the unit hypercube. 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.