Clustering methods for large scale geometrical global optimization. (English) Zbl 1429.90053
Summary: 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.
MSC:
| 90C26 | Nonconvex programming, global optimization |
Keywords:
global optimization; clustering methods; multi level single linkage; feature space; Lennard-Jones clusters; Morse clusters; sphere packingReferences:
| [1] | Addis, B.; Locatelli, M.; Schoen, F., Disk packing in a square: A new global optimization approach, Informs J. Comput., 20, 516-524 (2008) · Zbl 1243.90084 · doi:10.1287/ijoc.1080.0263 |
| [2] | Addis, B.; Locatelli, M.; Schoen, F., Efficiently packing unequal disks in a circle, Oper. Res. Lett., 36, 37-42 (2008) · Zbl 1151.90035 · doi:10.1016/j.orl.2007.03.001 |
| [3] | Bagattini, F.; Schoen, F.; Tigli, L., Clustering methods for the optimization of atomic cluster structure, J. Chem. Phys., 148 (2018) · doi:10.1063/1.5020858 |
| [4] | Becker, R.W. and Lago, G.V., A global optimization algorithm, Proceedings of the 8th Allerton Conference on Circuits and Systems Theory, Monticello, Illinois. 1970, pp. 3-12. |
| [5] | Cheng, J.; Fournier, R., Structural optimization of atomic clusters by tabu search in descriptor space, Theor. Chem. Acc., 112, 7-15 (2004) · doi:10.1007/s00214-003-0552-1 |
| [6] | Cheng, L.; Feng, Y.; Yang, J.; Yang, J., Funnel hopping: Searching the cluster potential energy surface over the funnels, J. Chem. Phys., 130 (2009) |
| [7] | Dixon, L. C.W.; Szegö, G. P., Towards Global Optimization (1975), North-Holland, Amsterdam · Zbl 0309.90052 |
| [8] | Dixon, L. C.W.; Szegö, G. P., Towards Global Optimization 2 (1978), North-Holland, Amsterdam · Zbl 0385.00011 |
| [9] | Doye, J. P.K.; Wales, D. J., Structural consequences of the range of the interatomic potential a menagerie of clusters, J. Chem. Soc. Faraday Trans., 93, 4233-4243 (1997) · doi:10.1039/a706221d |
| [10] | Doye, J. P.K.; Leary, R. H.; Locatelli, M.; Schoen, F., Global optimization of Morse clusters by potential energy transformations, INFORMS J. Comput., 16, 371-379 (2004) · Zbl 1239.90085 · doi:10.1287/ijoc.1040.0084 |
| [11] | Fournier, R., Theoretical study of the structure of silver clusters, J. Chem. Phys., 115, 2165-2177 (2001) · doi:10.1063/1.1383288 |
| [12] | Gill, P. E.; Murray, W.; Saunders, M. A., SNOPT: an SQP algorithm for large-scale constrained optimization, SIAM Rev., 47, 99-131 (2005) · Zbl 1210.90176 · doi:10.1137/S0036144504446096 |
| [13] | Huang, W.; Ye, T., Greedy vacancy search algorithm for packing equal circles in a square, Oper Res. Lett., 38, 378-382 (2010) · Zbl 1202.90226 · doi:10.1016/j.orl.2010.07.004 |
| [14] | Keys, A.S., Iacovella, C.R., and Glotzer, S.C., Harmoni Order Parameters for Characterizing Complex Particle Morphologies, arXiv 1012.4527v1, University of Michigan, Ann Arbor, 2010. · Zbl 1231.82003 |
| [15] | Leary, R. H., Global optimization on funneling landscapes, J. Global Optim., 18, 367-383 (2000) · Zbl 0986.90038 · doi:10.1023/A:1026500301312 |
| [16] | Liu, D. C.; Nocedal, J., On the limited memory bfgs method for large scale optimization, Math. Program., 45, 503-528 (1989) · Zbl 0696.90048 · doi:10.1007/BF01589116 |
| [17] | Locatelli, M.; Raber, U., Packing equal circles in a square: A deterministic global optimization approach, Discrete Appl. Math., 122, 139-166 (2002) · Zbl 1019.90033 · doi:10.1016/S0166-218X(01)00359-6 |
| [18] | Locatelli, M.; Maischberger, M.; Schoen, F., Differential evolution methods based on local searches, Comput. Oper. Res., 43, 169-180 (2014) · Zbl 1348.90529 · doi:10.1016/j.cor.2013.09.010 |
| [19] | Locatelli, M.; Schoen, F., Fast global optimization of difficult Lennard-Jones clusters, Comput. Optim. Appl., 21, 55-70 (2002) · Zbl 0988.90054 · doi:10.1023/A:1013596313166 |
| [20] | Locatelli, M.; Schoen, F., Local search based heuristics for global optimization: atomic clusters and beyond, Eur. J. Oper. Res., 222, 1-9 (2012) · Zbl 1253.90218 · doi:10.1016/j.ejor.2012.04.010 |
| [21] | Locatelli, M. and Schoen, F., Global Optimization: Theory, Algorithms, and Applications, MOS-SIAM Series on Optimization Vol. MO15, Society for Industrial and Applied Mathematics and the Mathematical Optimization Society, Philadelphia, USA, 2013. · Zbl 1286.90003 |
| [22] | Lôpez, C. O.; Beasley, J. E., A heuristic for the circle packing problem with a variety of containers, Eur. J. Oper. Res., 214, 512-525 (2011) · Zbl 1226.90088 · doi:10.1016/j.ejor.2011.04.024 |
| [23] | Markt, M.; Csendes, T., A new verified optimization technique for the ‘acking circles in a unit square’ problems, SIAM J. Optim., 16, 193-219 (2006) · Zbl 1089.90045 · doi:10.1137/S1052623403425617 |
| [24] | Rinnooy Kan, A. H.G.; Timmer, G. T., Stochastic global optimization methods. Part I: Clustering methods, Math. Program., 39, 27-56 (1987) · Zbl 0634.90066 · doi:10.1007/BF02592070 |
| [25] | Rinnooy Kan, A. H.G.; Timmer, G. T., Stochastic global optimization methods. Part II: Multi level methods, Math. Program., 39, 57-78 (1987) · Zbl 0634.90067 · doi:10.1007/BF02592071 |
| [26] | Schaer, J., On the densest packing of spheres in a cube, Canad. Math. Bull., 9, 265-270 (1966) · Zbl 0144.21402 · doi:10.4153/CMB-1966-033-0 |
| [27] | Schaer, J., The densest packing of ten congruent spheres in a cube, Intuitive Geometry (Szeged, 1991), 63, 403-424 (1994) · Zbl 0819.52016 |
| [28] | Shao, X.; Cheng, L.; Cai, W., A dynamic lattice searching method for fast optimization of Lennard-Jones clusters, J. Comput. Chem., 25, 1693-1698 (2004) · doi:10.1002/jcc.20096 |
| [29] | Shao, X.; Jiang, H.; Cai, W., Parallel random tunneling algorithm for structural optimization of Lennard-Jones clusters up to n=330, J. Chem. Inf. Comput. Sci., 44, 193-199 (2004) · doi:10.1021/ci0340862 |
| [30] | Steinhardt, P. J.; Nelson, D. R.; Ronchetti, M., Bond-orientational order in liquids and glasses, Phys. Rev. B, 28, 784 (1983) · doi:10.1103/PhysRevB.28.784 |
| [31] | Strandburg, K. J., Bond-orientational Order in Condensed Matter Systems (1992), Springer-Verlag: Springer-Verlag, New York |
| [32] | Szabó, P. G.; Markót, M. C.; Csendes, T.; Specht, E.; Casado, L. G.; Garcäa, I., New Approaches to Circle Packing in a Square: With Program Codes (Springer Optimization and Its Applications) (2007), Springer-Verlag New York Inc.: Springer-Verlag New York Inc., Secaucus, NJ, USA · Zbl 1128.52012 |
| [33] | Takeuchi, H., Clever and efficient method for searching optimal geometries of Lennard-Jones clusters, J. Chem. Inf. Model., 46, 2066-2070 (2006) · doi:10.1021/ci600206k |
| [34] | Törn, A. A., Cluster analysis using seed points and density-determined hyperspheres as an aid to global optimization, IEEE Trans. Syst. Man. Cybern., 7, 610-616 (1977) · Zbl 0361.62053 · doi:10.1109/TSMC.1977.4309787 |
| [35] | Törn, A. A.; Dixon, L. C.W.; Szegö, G. P., A search clustering approach to global optimization, Towards Global Optimization 2, 49-62 (1978), North-Holland: North-Holland, Amsterdam · Zbl 0392.90073 |
| [36] | Wales, D. J.; Doye, J. P.K., Global optimization by basin-hopping and the lowest energy structures of Lennard-Jones clusters containing up to 110 atoms, J. Phys. Chem. A, 101, 5111-5116 (1997) · doi:10.1021/jp970984n |
| [37] | Wang, Y.; Teitel, S.; Dellago, C., Melting of icosahedral gold nanoclusters from molecular dynamics simulations, J. Chem. Phys., 122 (2005) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
