×

zbMATH — the first resource for mathematics

Improving the convergence rate of the DIRECT global optimization algorithm. (English) Zbl 1370.90193
Summary: DIRECT is derivative-free global-search algorithm has been found to perform robustly across a wide variety of low-dimensional test problems. The reason DIRECT’s robustness is its lack of algorithmic parameters that need be “tuned” to make the algorithm perform well. In particular, there is no parameter that determines the relative emphasis on global versus local search. Unfortunately, the same algorithmic features that enable DIRECT to perform so robustly have a negative side effect. In particular, DIRECT is usually quick to get close to the global minimum, but very slow to refine the solution to high accuracy. This is what we call DIRECT’s “eventually inefficient behavior”. In this paper, we outline two root causes for this undesirable behavior and propose modifications to eliminate it. The paper builds upon our previously published “MrDIRECT” algorithm, which we can now show only addressed the first root cause of the “eventually inefficient behavior”. The key contribution of the current paper is a further enhancement that allows MrDIRECT to address the second root cause as well. To demonstrate the effectiveness of the enhanced MrDIRECT, we have identified a set of test functions that highlight different situations in which DIRECT has convergence issues. Extensive numerical work with this test suite demonstrates that the enhanced version of MrDIRECT does indeed improve the convergence rate of DIRECT.

MSC:
90C26 Nonconvex programming, global optimization
90C56 Derivative-free methods and methods using generalized derivatives
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Björkman, M; Holmström, K, Global optimization using the DIRECT algorithm in Matlab, Adv. Model. Optim., 1, 17-37, (1999) · Zbl 1115.90300
[2] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[3] Elsakov, SM; Shiryaev, VI, Homogeneous algorithms for multiextremal optimization, Comput. Math. Math. Phys., 50, 1642-1654, (2010) · Zbl 1224.90152
[4] Finkel D.E.: Global optimization with the DIRECT algorithm. PHD thesis, North Carolina State University (2005) · Zbl 1187.90275
[5] Finkel, DE; Kelley, CT, Additive scaling and the DIRECT algorithm, J. Global Optim., 36, 597-608, (2006) · Zbl 1142.90488
[6] Floudas, CA; Gounaris, CE, A review of recent advances in global optimization, J. Global Optim., 45, 3-38, (2009) · Zbl 1180.90245
[7] 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., 9, 469-480, (2003) · Zbl 1068.90600
[8] Gaviano, M; Lera, D, Test functions with variable attraction regions for global optimization problems, J. Global Optim., 13, 207-223, (1998) · Zbl 0912.90254
[9] Gablonsky, JM; Kelley, CT, A locally-biased form of the DIRECT algorithm, J. Global Optim., 21, 27-37, (2001) · Zbl 1039.90049
[10] Hedar A.: http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar_files/TestGO.htm · Zbl 1225.90162
[11] He, J; Watson, LT; etal., Dynamic data structures for a direct search algorithm, Comput. Optim. Appl., 23, 5-25, (2002) · Zbl 1036.90055
[12] Holland, J.H.: Adaption in Nature and Artificial Systems, 2nd edn. MIT Press, Cambrige, MA (1992)
[13] Holmstrom, K., Goran A.O., Edvall M.M.: User’s Guide for TOMLAB 7. Tomlab optimization. http://tomopt.com · Zbl 1297.90130
[14] Huyer, W; Neumaier, A, Global optimization by multilevel coordinate search, J. Global Optim., 14, 331-355, (1999) · Zbl 0956.90045
[15] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181, (1993) · Zbl 0796.49032
[16] Jones, D.R.: The DIRECT global optimization algorithm. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of optimization. Kluwer Academic, Dordrecht (2001) · Zbl 1272.90116
[17] Kirkpatrick, S; Gelatt, CD; Vecchi, MP, Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[18] Lera, D; Sergeyev, YD, Deterministic global optimization using space-filling curves and multiple estimates of Lipschitz and H\(\ddot{o}\)lder constants, Commun. Nonlinear Sci. Numer. Simul., 23, 328-342, (2015) · Zbl 1356.90112
[19] Liang J.J.: Novel particle swarm optimizers with hybrid, dynamic & adaptive neighborhood structures. PhD thesis, Nanyang Technological University, Singapore (2008) · Zbl 1068.90600
[20] Liang J.J., Qu B.Y., Suganthan P.N.: Problem definitions and evaluation criteria for the CEC 2013 special session and competition on real-parameter optimization. Technical Report 201212, Computational Intelligence Laboratory, Zhengzhou University, Zhengzhou China and Technical Report, Nanyang Technological University, Singapore, January (2013) · Zbl 1312.90062
[21] Liu, QF, Linear scaling and the DIRECT algorithm, J. Global Optim., 56, 1233-1245, (2013) · Zbl 1272.90060
[22] Liu, QF; Cheng, WY, A modified DIRECT algorithm with bilevel partition, J. Global Optim., 60, 483-499, (2014) · Zbl 1303.90083
[23] Liu, QF; Zeng, JP, Global optimization by multilevel partition, J. Global Optim., 61, 47-69, (2015) · Zbl 1312.90062
[24] Liu, QF; Zeng, JP; Yang, G, Mrdirect: a multilevel robust DIRECT algorithm for global optimization problems, J. Global Optim., 62, 205-227, (2015) · Zbl 1326.90065
[25] 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
[26] Liuzzi, G; Lucidi, S; Piccialli, V, A partion-based global optimization algorithm, J. Global Optim., 48, 113-128, (2010) · Zbl 1230.90153
[27] Liuzzi, G., Lucidi, S., Piccialli, V.: Exploiting derivative-free local searches in DIRECT-type algorithms for global optimization. Comput. Optim. Appl. (2015). doi:10.1007/s10589-015-9741-9 · Zbl 1370.90194
[28] Ljunberg, K; Holmgren, S, Simultaneous search for multiple QTL using the global optimization algorithm DIRECT, Bioinformatics, 20, 1887-1895, (2004)
[29] Moré, J; Wild, S, Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 172-191, (2009) · Zbl 1187.90319
[30] Pardalos, P.M., Schoen, F.: Recent advances and trends in global optimization: deterministic and stochastic methods. In: Proceedings of the Sixth International Conference on Foundations of Computer-Aided Process Design, DSI, vol. 1, pp. 119-131 (2004) · Zbl 1187.90319
[31] Paulavic̆ius, R; Sergeyev, YD; Kvasov, DE; Z̆ilinskas, J, Globally-biased disimpl algorithm for expensive global optimization, J. Global Optim., 59, 545-567, (2014) · Zbl 1297.90130
[32] Rios, LM; Sahinidis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Global Optim., 56, 1247-1293, (2013) · Zbl 1272.90116
[33] Sergeyev, YD; Kvasov, DE, Global search based on efficient diagonal partitions and a set of Lipschitz constants, SIAM J. Optim., 16, 910-937, (2006) · Zbl 1097.65068
[34] Žilinskas, A, On strong homogeneity of two global optimization algorithms based on statistical models of multimodal objective functions, Appl. Math. Comput., 218, 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.