×

zbMATH — the first resource for mathematics

The DIRECT algorithm: 25 years later. (English) Zbl 07340951
Summary: Introduced in 1993, the DIRECT global optimization algorithm provided a fresh approach to minimizing a black-box function subject to lower and upper bounds on the variables. In contrast to the plethora of nature-inspired heuristics, DIRECT was deterministic and had only one hyperparameter (the desired accuracy). Moreover, the algorithm was simple, easy to implement, and usually performed well on low-dimensional problems (up to six variables). Most importantly, DIRECT balanced local and global search (exploitation vs. exploration) in a unique way: in each iteration, several points were sampled, some for global and some for local search. This approach eliminated the need for “tuning parameters” that set the balance between local and global search. However, the very same features that made DIRECT simple and conceptually attractive also created weaknesses. For example, it was commonly observed that, while DIRECT is often fast to find the basin of the global optimum, it can be slow to fine-tune the solution to high accuracy. In this paper, we identify several such weaknesses and survey the work of various researchers to extend DIRECT so that it performs better. All of the extensions show substantial improvement over DIRECT on various test functions. An outstanding challenge is to improve performance robustly across problems of different degrees of difficulty, ranging from simple (unimodal, few variables) to very hard (multimodal, sharply peaked, many variables). Opportunities for further improvement may lie in combining the best features of the different extensions.
MSC:
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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
[2] Belfkira, R.; Zhang, L.; Barakat, G., Optimal sizing study of hybrid wind/PV/diesel power generation unit, Solar Energy, 85, 1, 100-110 (2011)
[3] Campana, EF; Diez, M.; Iemma, U.; Liuzzi, G.; Lucidi, S.; Rinaldi, F.; Serani, A., Derivative-free global ship design optimization using global/local hybridization of the DIRECT algorithm, Optim. Eng., 17, 1, 127-156 (2016) · Zbl 1365.90213
[4] Cappellari, M.; Verolme, EK; van der Marel, RP; Kleijn, GAV; Illingworth, GD; Franx, M.; Carollo, CM; deZeeuw, PT, The counterrotating core and the black hole mass of IC 1459, Astrophys. J., 578, 2, 787-805 (2002)
[5] 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
[6] Chang, Y.; Hung, K.; Lee, S., Human face detection with neural networks and the DIRECT algorithm, Artif. Life Robot., 12, 1, 112 (2008)
[7] Costa, MFP; Rocha, AMA; Fernandes, EM, Filter-based DIRECT method for constrained global optimization, J. Glob. Optim., 71, 3, 517-536 (2018) · Zbl 1402.90127
[8] 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
[9] Deng, G., Ferris, M.C.: Extension of the DIRECT optimization algorithm for noisy functions. In:Proceedings of the 39th Conference on Winter Simulation: 40 Years! The Best is Yet to Come (WSC’07), pp. 497-504. IEEE Press, Piscataway (2007). http://dl.acm.org/citation.cfm?id=1351542.1351641
[10] Di Pillo, G.; Lucidi, S.; Rinaldi, F., A derivative-free algorithm for constrained global optimization based on exact penalty functions, J. Optim. Theory Appl., 164, 3, 862-882 (2015) · Zbl 1330.90085
[11] Di Pillo, G.; Liuzzi, G.; Lucidi, S.; Piccialli, V.; Rinaldi, F., A DIRECT-type approach for derivative-free constrained global optimization, Comput. Optim. Appl., 65, 2, 361-397 (2016) · Zbl 1370.90189
[12] Elsakov, SM; Shiryaev, VI, Homogeneous algorithms for multiextremal optimization, Comput. Math. Math. Phys., 50, 10, 1642-1654 (2010) · Zbl 1224.90152
[13] Fellini, R., Michelena, N., Papalambros, P., Sasena, M.: Optimal design of automotive hybrid powertrain systems. In: Proceedings First International Symposium on Environmentally Conscious Design and Inverse Manufacturing, pp. 400-405 (1999). doi:10.1109/ECODIM.1999.747645
[14] Finkel, DE; Kelley, CT, Additive scaling and the DIRECT algorithm, J. Glob. Optim., 36, 4, 597-608 (2006) · Zbl 1142.90488
[15] Finkel, D.E., Kelly, C.T.: An adaptive restart implementation of DIRECT. Technical report, Technical report CRSC-TR04-30, Center for Research in Scientific Computation, North Carolina State University, Raleigh (2004). https://repository.lib.ncsu.edu/bitstream/handle/1840.4/461/crsc-tr04-30.pdf?sequence=1
[16] Fletcher, R.; Leyffer, S., Nonlinear programming without a penalty function, Math. Program., 269, 239-269 (2002) · Zbl 1049.90088
[17] Gablonsky, J.: Modifications of the DIRECT Algorithm. PhD thesis, North Carolina State University, Raleigh (2001). https://repository.lib.ncsu.edu/handle/1840.16/3920 · Zbl 1039.90049
[18] Gablonsky, J.; Kelly, CT, A locally-biased form of the DIRECT algorithm, J. Glob. Optim., 21, 1, 27-37 (2001) · Zbl 1039.90049
[19] 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., 29, 4, 469-480 (2003) · Zbl 1068.90600
[20] Gillard, JW; Kvasov, DE, Lipschitz optimization methods for fitting a sum of damped sinusoids to a series of observations, Stat. Its Interface, 10, 1, 59-70 (2017) · Zbl 1387.90196
[21] Grbić, R.; Nyarko, EK; Scitovski, R., A modification of the DIRECT method for Lipschitz global optimization for a symmetric function, J. Glob. Optim., 57, 4, 1193-1212 (2013) · Zbl 1279.65076
[22] Hansen, P.; Jaumard, B.; Horst, R.; Pardalos, PM, Lipschitz optimization, Handbook of Global Optimization, 407-493 (1995), Boston: Springer, Boston · Zbl 0833.90105
[23] Hansen, P.; Jaumard, B.; Lu, SH, On using estimates of Lipschitz constants in global optimization, J. Optim. Theory Appl., 75, 1, 195-200 (1992) · Zbl 0795.90065
[24] Hao, J.; Yu, Z.; Zhao, Z.; Shen, P.; Zhan, X., Optimization of key parameters of energy management strategy for hybrid electric vehicle using DIRECT algorithm, Energies, 9, 12, 997 (2016)
[25] Hedar, A.: Global Optimization Test Problems. http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO.htm (2020)
[26] Holmström, K.: TOMLAB GlcCluster. http://tomwiki.com/GlcCluster#Description/
[27] Huyer, W.; Neumaier, A., Global optimization by multilevel coordinate search, J. Glob. Optim., 14, 4, 331-355 (1999) · Zbl 0956.90045
[28] Jarvis, RA, On the identification of the convex hull of a finite set of points in the plane, Inf. Process. Lett., 2, 1, 18-21 (1973) · Zbl 0256.68041
[29] Jones, D.R.: Direct global optimization algorithm. In: Floudas, C.A., Pardalos, P.M. (Eds.) Encyclopedia of Optimization, pp. 431-440. Springer, Boston (2001). doi:10.1007/0-306-48332-7_93
[30] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 1, 157-181 (1993) · Zbl 0796.49032
[31] Kokail, C.; Maier, C.; van Bijnen, R.; Brydges, T.; Joshi, MK; Jurcevic, P.; Muschik, CA; Silvi, P.; Blatt, R.; Roos, CF; Zoller, P., Self-verifying variational quantum simulation of lattice models, Nature, 569, 7756, 355-360 (2019)
[32] Kvasov, DE; Pizzuti, C.; Sergeyev, YD, Local tuning and partition strategies for diagonal GO methods, Numer. Math., 94, 1, 93-106 (2003) · Zbl 1056.65059
[33] Kvasov, DE, Multidimensional lipschitz global optimization based on efficient diagonal partitions, 4OR, 6, 403-406 (2008) · Zbl 1179.90263
[34] Kvasov, DE; Menniti, D.; Pinnarelli, A.; Sergeyev, YD; Sorrentino, N., Tuning fuzzy power-system stabilizers in multi-machine systems by global optimization algorithms based on efficient domain partitions, Electr. Power Syst. Res., 78, 7, 1217-1229 (2008)
[35] Lang, H.; Liu, L.; Yang, Q., Design of URAs by DIRECT global optimization algorithm, Optik, 120, 8, 370-373 (2009)
[36] Liu, H.; Xu, S.; Wang, X.; Wu, J.; Song, Y., A global optimization algorithm for simulation-based problems via the extended DIRECT scheme, Eng. Optim., 47, 11, 1441-1458 (2015)
[37] Liu, H.; Xu, S.; Chen, X.; Wang, X.; Ma, Q., Constrained global optimization via a DIRECT-type constraint-handling technique and an adaptive metamodeling strategy, Struct. Multidiscip. Optim., 55, 1, 155-177 (2017)
[38] 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
[39] Liu, Q.; Yang, G.; Zhang, Z.; Zeng, J., Improving the convergence rate of the DIRECT global optimization algorithm, J. Glob. Optim., 67, 4, 851-872 (2017) · Zbl 1370.90193
[40] 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, 2, 353-375 (2010) · Zbl 1187.90275
[41] Liuzzi, G.; Lucidi, S.; Piccialli, V., Exploiting derivative-free local searches in DIRECT-type algorithms for global optimization, Comput. Optim. Appl., 65, 2, 449-475 (2016) · Zbl 1370.90194
[42] Ljungberg, K.; Holmgren, S.; Carlborg, Ö., Simultaneous search for multiple QTL using the global optimization algorithm DIRECT, Bioinformatics, 20, 12, 1887-1895 (2004)
[43] Lovison, A.; Miettinen, K., Exact extension of the DIRECT algorithm to multiple objectives, AIP Conf. Proc., 2070, 1, 020053 (2019)
[44] Marot, J.; Bourennane, S., Subspace-based and DIRECT algorithms for distorted circular contour estimation, IEEE Trans. Image Process., 16, 9, 2369-2378 (2007) · Zbl 1168.94425
[45] Mockus, J., On the pareto optimality in the context of Lipschitzian optimization, Informatica, 22, 4, 521-536 (2011) · Zbl 1272.90061
[46] 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, 425-450 (2017) · Zbl 1359.90131
[47] Moles, CG; Mendes, P.; Banga, JR, Parameter estimation in biochemical pathways: a comparison of global optimization methods, Genome Res., 13, 11, 2467-2474 (2003)
[48] Na, J.; Lim, Y.; Han, C., A modified DIRECT algorithm for hidden constraints in an LNG process optimization, Energy, 126, 488-500 (2017)
[49] Nguyen, TL; Low, K., A global maximum power point tracking scheme employing DIRECT search algorithm for photovoltaic systems, IEEE Trans. Ind. Electron., 57, 10, 3456-3467 (2010)
[50] Paulavičius, R., Žilinskas, J.: Simplicial Lipschitz optimization without Lipschitz constant. In: Simplicial Global Optimization, pp. 61-86. Springer, New York (2014) doi:10.1007/978-1-4614-9093-7_3 · Zbl 1300.90031
[51] Paulavičius, R.; Sergeyev, YD; Kvasov, DE; Žilinskas, J., Globally-biased DISIMPL algorithm for expensive global optimization, J. Glob. Optim., 59, 2, 545-567 (2014) · Zbl 1297.90130
[52] 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
[53] Paulavičius, R.; Sergeyev, YD; Kvasov, DE; Žilinskas, J., Globally-biased BIRECT algorithm with local accelerators for expensive global optimization, Expert Syst. Appl., 144, 113052 (2020)
[54] Pintér, JD; Pardalos, P., Global optimization in action, Nonconvex Optimization and its Applications, vol. 6. (1996), USA: Springer, USA
[55] Piyavskii, SA, An algorithm for finding the absolute extremum of a function, USSR Comput. Math. Math. Phys., 12, 4, 57-67 (1972) · Zbl 0282.65052
[56] Powell, M.J.D.: The BOBYQA algorithm for bound constrained optimization without derivatives. Technical report, Department of Applied Mathematics and Theoretical Physics, University of Cambridge (2009). http://www.damtp.cam.ac.uk/user/na/NA_papers/NA2009_06.pdf
[57] Rios, LM; Sahinidis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Glob. Optim., 56, 1247-1293 (2013) · Zbl 1272.90116
[58] Ruf, F., Neiss, A., Barthels, A., Kohler, T.P.,Michel, H., Froeschl, J., Herzog, H.: Design optimization of a 14 V| automotive power net using a parallelized DIRECT algorithm in a physical simulation. In: 2012 13th International Conference on Optimization of Electrical and Electronic Equipment (OPTIM), pp. 73-80 (2012). doi:10.1109/OPTIM.2012.6231911
[59] Scitovski, Rudolf; Sabo, Kristian, Application of the DIRECT algorithm to searching for an optimal \(k\)-partition of the set \(a \in r^n\) and its application to the multiple circle detection problem, J. Glob. Optim., 74, 1, 63-77 (2019) · Zbl 1461.65185
[60] Sergeyev, YD, An information global optimization algorithm with local tuning, SIAM J. Optim., 5, 4, 858-870 (1995) · Zbl 0847.90128
[61] Sergeyev, YD, Global one-dimensional optimization using smooth auxiliary functions, Math. Program., 81, 1, 127-146 (1998) · Zbl 0920.90133
[62] Sergeyev, YD, Efficient strategy for adaptive partition of n-dimensional intervals in the framework of diagonal algorithms, J. Optim. Theory Appl., 107, 1, 145-168 (2000) · Zbl 0969.90068
[63] Sergeyev, YD; Kvasov, DE, Global search based on efficient diagonal partitions and a set of Lipschitz constants, SIAM J. Optim., 16, 3, 910-937 (2006) · Zbl 1097.65068
[64] Sergeyev, Y.D., Kvasov, D.E.: Deterministic Global Optimization: An Introduction to the Diagonal Approach. Springer Briefs in Optimization. Springer, Berlin (2017). doi:10.1007/978-1-4939-7199-2 · Zbl 1371.90112
[65] Sergeyev, YD; Kvasov, DE; Mukhametzhanov, MS, On the efficiency of nature-inspired metaheuristics in expensive global optimization with limited budget, Sci. Rep., 8, 1, 453 (2018)
[66] Sergeyev, YD; Kvasov, DE; Mukhametzhanov, MS, On strong homogeneity of a class of global optimization algorithms working with infinite and infinitesimal scales, Commun. Nonlinear Sci. Numer. Simul., 59, 319-330 (2018) · Zbl 07263346
[67] Shubert, B., A sequential method seeking the global maximum of a function, SIAM J. Numer. Anal., 9, 3, 379-388 (1972) · Zbl 0251.65052
[68] 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
[69] 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)
[70] Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-convex Constraints: Sequential and Parallel Algorithms, Volume 45 of Nonconvex Optimization and Its Applications. Springer, US (2000). doi:10.1007/978-1-4615-4677-1 · Zbl 0987.90068
[71] Svensson, B., Nia, N.K., Danielsson, F., Lennartson, B.: Sheet-metal press line parameter tuning using a combined DIRECT and Nelder-Mead algorithm. In: ETFA2011, pp. 1-8 (2011). doi:10.1109/ETFA.2011.6059031
[72] Tao, Q.; Huang, X.; Wang, S.; Li, L., Adaptive block coordinate DIRECT algorithm, J. Glob. Optim., 69, 4, 797-822 (2017) · Zbl 1385.90022
[73] Tavassoli, A.; Hajikolaei, KH; Sadeqi, S.; Wang, GG; Kjeang, E., Modification of DIRECT for high-dimensional design problems, Eng. Optim., 46, 6, 810-823 (2014)
[74] Wipke, K., Markel, T., Nelson, D.: Optimizing energy management strategy and a degree of hybridization for a hydrogen fuel cell SUV. In: Proceedings of the 18th Electric Vehicle Symposium(EVS-18), Berlin, Germany (2001). https://pdfs.semanticscholar.org/b1cd/d6b0ab88dd50b2d228854bd9de3512785444.pdf
[75] Wong, C.S.Y., Al-Dujaili, A., Sundaram, S.: Hypervolume-based DIRECT for multi-objective optimisation. In: Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion, GECCO’16 Companion, pp. 1201-1208 (2016). ACM, New York. doi:10.1145/2908961.2931702
[76] Xiao, Yiming; Rivaz, Hassan; Chabanas, Matthieu; Fortin, Maryse; Machado, Ines; Yangming, Ou; Heinrich, Mattias P.; Schnabel, Julia A.; Zhong, Xia; Maier, Andreas, Evaluation of MRI to ultrasound registration methods for brain shift correction: the CuRIOUS2018 challenge, IEEE Trans. Med. Imaging, 39, 3, 777-786 (2020)
[77] Zhu, H.; Bogy, DB, DIRECT algorithm and its application to slider air-bearing surface optimization, IEEE Trans. Magn., 38, 5, 2168-2170 (2002)
[78] Žilinskas, A., On strong homogeneity of two global optimization algorithms based on statistical models of multimodal objective functions, Appl. Math. Comput., 218, 16, 8131-8136 (2012) · Zbl 1245.90094
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.