An empirical study of various candidate selection and partitioning techniques in the DIRECT framework. (English) Zbl 07822728
Summary: Over the last three decades, many attempts have been made to improve the DIRECT (DIviding RECTangles) algorithm’s efficiency. Various novel ideas and extensions have been suggested. The main two steps of DIRECT-type algorithms are selecting and partitioning potentially optimal rectangles. However, the most efficient combination of these two steps is an area that has not been investigated so far. This paper presents a study covering an extensive examination of various candidate selection and partitioning techniques within the same DIRECT algorithmic framework. Twelve DIRECT-type algorithmic variations are compared on 800 randomly generated GKLS-type test problems and 96 box-constrained global optimization problems from DIRECTGOLib v1.1 with varying complexity. Based on these studies, we have identified the most efficient selection and partitioning combinations leading to new, more efficient, DIRECT-type algorithms. All these algorithms are included in the latest version of DIRECTGO v1.1.0 and are publicly available.
MSC:
| 90C26 | Nonconvex programming, global optimization |
| 90C56 | Derivative-free methods and methods using generalized derivatives |
Software:
MCS; Virtual library; LGO; Global Optimization Test; VTDIRECT95; DIRECTGO; DIRECTGOLib; MrDIRECT; AMPGO; Algorithm 829; GitHub; DIRECT; MultiMinReferences:
| [1] | Baker, C.A., Watson, L.T., Grossman, B., Mason, W.H., Haftka, R.T.: Parallel global aircraft configuration design space exploration. In: A. Tentner (ed.) High Performance Computing Symposium 2000, pp. 54-66. Soc. for Computer Simulation Internat (2000) |
| [2] | Bartholomew-Biggs, MC; Parkhurst, SC; Wilson, SP, Using DIRECT to solve an aircraft routing problem, Comput. Optim. Appl., 21, 3, 311-323, 2002 · Zbl 1017.90133 · doi:10.1023/A:1013729320435 |
| [3] | Carter, RG; Gablonsky, JM; Patrick, A.; Kelley, CT; Eslinger, OJ, Algorithms for noisy problems in gas transmission pipeline optimization, Optim. Eng., 2, 2, 139-157, 2001 · Zbl 1079.90624 · doi:10.1023/A:1013123110266 |
| [4] | Clerc, M.: The swarm and the queen: towards a deterministic and adaptive particle swarm optimization. In: Proceedings of the 1999 Congress on Evolutionary Computation, CEC 1999 (1999). doi:10.1109/CEC.1999.785513 |
| [5] | Cox, SE; Haftka, RT; Baker, CA; Grossman, B.; Mason, WH; Watson, LT, A comparison of global optimization methods for the design of a high-speed civil transport, J. Glob. Optim., 21, 4, 415-432, 2001 · Zbl 1014.90072 · doi:10.1023/A:1012782825166 |
| [6] | Di Serafino, D.; Liuzzi, G.; Piccialli, V.; Riccio, F.; Toraldo, G., A modified DIviding RECTangles algorithm for a problem in astrophysics, J. Optim. Theory Appl., 151, 1, 175-190, 2011 · Zbl 1226.90082 · doi:10.1007/s10957-011-9856-9 |
| [7] | Dixon, L., Szegö, C.: The global optimisation problem: An introduction. In: L. Dixon, G. Szegö (eds.) Towards Global Optimization, vol. 2, pp. 1-15. North-Holland Publishing Company (1978) |
| [8] | Finkel, D.E., Kelley, C.T.: An adaptive restart implementation of direct. Technical report CRSC-TR04-30, Center for Research in Scientific Computation, North Carolina State University, Raleigh (2004) |
| [9] | Finkel, DE; Kelley, CT, Additive scaling and the DIRECT algorithm, J. Glob. Optim., 36, 4, 597-608, 2006 · Zbl 1142.90488 · doi:10.1007/s10898-006-9029-9 |
| [10] | Gablonsky, J.M.: Modifications of the DIRECT algorithm. Ph.D. thesis, North Carolina State University (2001) |
| [11] | Gablonsky, JM; Kelley, CT, A locally-biased form of the DIRECT algorithm, J. Glob. Optim., 21, 1, 27-37, 2001 · Zbl 1039.90049 · doi:10.1023/A:1017930332101 |
| [12] | Gavana, A.: Global optimization benchmarks and ampgo. http://infinity77.net/global_optimization/index.html. Online; accessed: 2021-07-22 |
| [13] | Gaviano, M.; Kvasov, DE; Lera, D.; Sergeyev, YD, Algorithm 829: Software for generation of classes of test functions with known local and global minima for global optimization, ACM Trans. Math. Softw. (TOMS), 29, 4, 469-480, 2003 · Zbl 1068.90600 · doi:10.1145/962437.962444 |
| [14] | Grishagin, V.A.: Operating characteristics of some global search algorithms. In: Problems of Stochastic Search, vol. 7, pp. 198-206. Zinatne, Riga. In Russian (1978) · Zbl 0442.90087 |
| [15] | He, J.; Verstak, A.; Sosonkina, M.; Watson, LT, Performance modeling and analysis of a massively parallel DIRECT-Part 2, Int. J. High Perform. Comput. Appl., 23, 1, 29-41, 2009 · doi:10.1177/1094342008098463 |
| [16] | He, J.; Verstak, A.; Watson, LT; Sosonkina, M., Design and implementation of a massively parallel version of direct, Comput. Optim. Appl., 2008 · Zbl 1181.90138 · doi:10.1007/s10589-007-9092-2 |
| [17] | He, J.; Verstak, A.; Watson, LT; Sosonkina, M., Performance modeling and analysis of a massively parallel DIRECT-part 1, Int. J. High Perform. Comput. Appl., 23, 1, 14-28, 2009 · doi:10.1177/1094342008098462 |
| [18] | He, J.; Watson, LT; Sosonkina, M., Algorithm 897: VTDIRECT95: serial and parallel codes for the global optimization algorithm DIRECT, ACM Trans. Math. Softw., 2010 · Zbl 1364.65127 · doi:10.1145/1527286.1527291 |
| [19] | Hedar, A.: Test functions for unconstrained global optimization. http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO.htm (2005). Online; accessed: 2017-03-22 |
| [20] | Horst, R., Pardalos, P.M., Thoai, N.V.: Introduction to Global Optimization. Kluwer Academic Publishers, Nonconvex Optimization and Its Application (1995) · Zbl 0836.90134 |
| [21] | Huyer, W.; Neumaier, A., Global optimization by multilevel coordinate search, J. Glob. Optim., 14, 4, 331-355, 1999 · Zbl 0956.90045 · doi:10.1023/A:1008382309369 |
| [22] | John, H., Adaptation in Natural and Artificial Systems, 1975, Ann Arbor: The University of Michigan Press, Ann Arbor · Zbl 0317.68006 |
| [23] | Jones, DR; Floudas, CA; Pardalos, PM, The Direct global optimization algorithm, The Encyclopedia of Optimization, 431-440, 2001, Dordrect: Kluwer Academic Publishers, Dordrect · Zbl 1027.90001 · doi:10.1007/0-306-48332-7_93 |
| [24] | Jones, DR; Martins, JRRA, The DIRECT algorithm: 25 years Later, J. Glob. Optim., 79, 3, 521-566, 2021 · Zbl 1466.90076 · doi:10.1007/s10898-020-00952-6 |
| [25] | Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 1, 157-181, 1993 · Zbl 0796.49032 · doi:10.1007/BF00941892 |
| [26] | Kennedy, J., Eberhart, R.: Particle swarm optimization. In Proceedings of the IEEE International Conference on Neural Networks IV pp. 1942-1948 (1995). doi:10.1109/ICNN.1995.488968 |
| [27] | Kirkpatrick, S.; Gelatt, CD; Vecchi, MP, Optimization by simulated annealing, Science, 1983 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [28] | Liu, H.; Xu, S.; Wang, X.; Wu, X.; Song, Y., A global optimization algorithm for simulation-based problems via the extended direct scheme, Eng. Optim., 47, 11, 1441-1458, 2015 · doi:10.1080/0305215X.2014.971777 |
| [29] | Liu, Q., Linear scaling and the direct algorithm, J. Glob. Optim., 56, 1233-1245, 2013 · Zbl 1272.90060 · doi:10.1007/s10898-012-9952-x |
| [30] | Liu, Q.; Zeng, J.; Yang, G., MrDIRECT: a multilevel robust DIRECT algorithm for global optimization problems, J. Glob. Optim., 62, 2, 205-227, 2015 · Zbl 1326.90065 · doi:10.1007/s10898-014-0241-8 |
| [31] | Liuzzi, G.; Lucidi, S.; Piccialli, V., A DIRECT-based approach exploiting local minimizations for the solution of large-scale global optimization problems, Comput. Optim. Appl., 45, 353-375, 2010 · Zbl 1187.90275 · doi:10.1007/s10589-008-9217-2 |
| [32] | Mockus, J.; Paulavičius, R.; Rusakevičius, D.; Šešok, D.; Žilinskas, J., Application of Reduced-set Pareto-Lipschitzian Optimization to truss optimization, J. Glob. Optim., 67, 1-2, 425-450, 2017 · Zbl 1359.90131 · doi:10.1007/s10898-015-0364-6 |
| [33] | Paulavičius, R.; Chiter, L.; Žilinskas, J., Global optimization based on bisection of rectangles, function values at diagonals, and a set of Lipschitz constants, J. Glob. Optim., 71, 1, 5-20, 2018 · Zbl 1402.90134 · doi:10.1007/s10898-016-0485-6 |
| [34] | Paulavičius, R.; Sergeyev, YD; Kvasov, DE; Žilinskas, J., Globally-biased DISIMPL algorithm for expensive global optimization, J. Glob. Optim., 59, 2-3, 545-567, 2014 · Zbl 1297.90130 · doi:10.1007/s10898-014-0180-4 |
| [35] | Paulavičius, R.; Sergeyev, YD; Kvasov, DE; Žilinskas, J., Globally-biased BIRECT algorithm with local accelerators for expensive global optimization, Expert Syst. Appl., 144, 11305, 2020 · doi:10.1016/j.eswa.2019.113052 |
| [36] | Paulavičius, R.; Žilinskas, J., Analysis of different norms and corresponding Lipschitz constants for global optimization, Technol. Econ. Dev. Econ., 36, 4, 383-387, 2006 · doi:10.1080/13928619.2006.9637758 |
| [37] | Paulavičius, R.; Žilinskas, J., Analysis of different norms and corresponding Lipschitz constants for global optimization in multidimensional case, Inf. Technol. Control, 36, 4, 383-387, 2007 |
| [38] | Paulavičius, R.; Žilinskas, J., Improved Lipschitz bounds with the first norm for function values over multidimensional simplex, Math. Model. Anal., 13, 4, 553-563, 2008 · Zbl 1182.90073 · doi:10.3846/1392-6292.2008.13.553-563 |
| [39] | Paulavičius, R.; Žilinskas, J., Global optimization using the branch-and-bound algorithm with a combination of Lipschitz bounds over simplices, Technol. Econ. Dev. Econ., 15, 2, 310-325, 2009 · doi:10.3846/1392-8619.2009.15.310-325 |
| [40] | Paulavičius, R.; Žilinskas, J., Simplicial Lipschitz optimization without the Lipschitz constant, J. Glob. Optim., 59, 1, 23-40, 2013 · Zbl 1300.90031 · doi:10.1007/s10898-013-0089-3 |
| [41] | Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. SpringerBriefs in Optimization. Springer New York, New York (2014). doi:10.1007/978-1-4614-9093-7 · Zbl 1401.90017 |
| [42] | Pintér, J.D.: Global optimization in action: continuous and Lipschitz optimization: algorithms, implementations and applications, Nonconvex Optimization and Its Applications, vol. 6. Springer US (1996). doi:10.1007/978-1-4757-2502-5 · Zbl 0842.90110 |
| [43] | Piyavskii, SA, An algorithm for finding the absolute minimum of a function, Theory Optim. Solut., 2, 13-24, 1967 · Zbl 0282.65052 · doi:10.1016/0041-5553(72)90115-2 |
| [44] | Rios, LM; Sahinidis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Glob. Optim., 56, 3, 1247-1293, 2007 · Zbl 1272.90116 · doi:10.1007/s10898-012-9951-y |
| [45] | Sergeyev, YD; Kvasov, DE, Global search based on diagonal partitions and a set of Lipschitz constants, SIAM J. Optim., 16, 3, 910-937, 2006 · Zbl 1097.65068 · doi:10.1137/040621132 |
| [46] | Sergeyev, YD; Kvasov, DE, Diagonal Global Optimization Methods, 2008, Moscow: FizMatLit, Moscow |
| [47] | Sergeyev, YD; Kvasov, DE; Cochran, JJ; Cox, LA; Keskinocak, P.; Kharoufeh, JP; Smith, JC, Lipschitz global optimization, Wiley Encyclopedia of Operations Research and Management Science (in 8 volumes), 2812-2828, 2011, New York: John Wiley and Sons, New York |
| [48] | Sergeyev, Y.D., Kvasov, D.E.: Deterministic global optimization: an introduction to the diagonal approach. In: SpringerBriefs in Optimization. Springer, Berlin (2017). doi:10.1007/978-1-4939-7199-2 · Zbl 1371.90112 |
| [49] | Shubert, BO, A sequential method seeking the global maximum of a function, SIAM J. Numer. Anal., 9, 379-388, 1972 · Zbl 0251.65052 · doi:10.1137/0709036 |
| [50] | Stripinis, L., Paulavičius, R.: DIRECTGO: A new DIRECT-type MATLAB toolbox for derivative-free global optimization (2022). arxiv:2107.02205 |
| [51] | Stripinis, L., Paulavičius, R.: DIRECTGO: A new DIRECT-type MATLAB toolbox for derivative-free global optimization. https://github.com/blockchain-group/DIRECTGO (2022) · Zbl 07908554 |
| [52] | Stripinis, L.; Paulavičius, R.; Žilinskas, J., Improved scheme for selection of potentially optimal hyper-rectangles in DIRECT, Optim. Lett., 12, 7, 1699-1712, 2018 · Zbl 1407.90264 · doi:10.1007/s11590-017-1228-4 |
| [53] | Stripinis, L.; Paulavičius, R.; Žilinskas, J., Penalty functions and two-step selection procedure based DIRECT-type algorithm for constrained global optimization, Struct. Multidiscip. Optim., 59, 6, 2155-2175, 2019 · doi:10.1007/s00158-018-2181-2 |
| [54] | Stripinis, L., Paulavičius, R.: DIRECTGOLib - DIRECT Global Optimization test problems Library, v1.0 (2022). doi:10.5281/zenodo.6491863 |
| [55] | Stripinis, L., Paulavičius, R.: DIRECTGOLib - DIRECT Global Optimization test problems Library, v1.1 (2022). doi:10.5281/zenodo.6491951 |
| [56] | Strongin, RG; Sergeyev, YD, Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms, 2000, Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 0987.90068 · doi:10.1007/978-1-4615-4677-1 |
| [57] | Surjanovic, S., Bingham, D.: Virtual library of simulation experiments: Test functions and datasets. http://www.sfu.ca/ ssurjano/index.html (2013). Online; accessed: 2017-03-22 |
| [58] | Watson, LT; Baker, CA, A fully-distributed parallel global search algorithm, Eng. Comput., 18, 1-2, 155-169, 2001 · Zbl 0999.74119 · doi:10.1108/02644400110365851 |
| [59] | Wolpert, D.; Macready, W., No free lunch theorems for optimization, IEEE Trans. Evol. Comput., 1, 1, 67-82, 1997 · doi:10.1109/4235.585893 |
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.
