# zbMATH — the first resource for mathematics

MSO: a framework for bound-constrained black-box global optimization algorithms. (English) Zbl 1394.90466
Summary: This paper addresses a class of algorithms for solving bound-constrained black-box global optimization problems. These algorithms partition the objective function domain over multiple scales in search for the global optimum. For such algorithms, we provide a generic procedure and refer to as multi-scale optimization (MSO). Furthermore, we propose a theoretical methodology to study the convergence of MSO algorithms based on three basic assumptions: (a) local Hölder continuity of the objective function $$f$$, (b) partitions boundedness, and (c) partitions sphericity. Moreover, the worst-case finite-time performance and convergence rate of several leading MSO algorithms, namely, Lipschitzian optimization methods, multi-level coordinate search, dividing rectangles, and optimistic optimization methods have been presented.

##### MSC:
 90C26 Nonconvex programming, global optimization
##### Software:
MSO; LGO; MCS ; Global Optimization Toolbox For Maple
Full Text:
##### References:
 [1] Archetti, F; Betrò, B, A priori analysis of deterministic strategies for global optimization problems, Towards Global Optim., 2, 31, (1978) · Zbl 0404.90082 [2] Auer, P; Cesa-Bianchi, N; Fischer, P, Finite-time analysis of the multiarmed bandit problem, Mach. Learn., 47, 235-256, (2002) · Zbl 1012.68093 [3] Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Athena Scientific, Belmont (1996) · Zbl 0572.90067 [4] Browne, CB; Powley, E; Whitehouse, D; Lucas, SM; Cowling, PI; Rohlfshagen, P; Tavener, S; Perez, D; Samothrakis, S; Colton, S, A survey of Monte Carlo tree search methods, IEEE Trans. Acoust. Speech Signal Process. Comput. Intell. AI Games, 4, 1-43, (2012) [5] Cesa-Bianchi, N., Lugosi, G.: Prediction, Learning, and Games. Cambridge University Press, Cambridge (2006) · Zbl 1114.91001 [6] Chaput, JC; Szostak, JW, Evolutionary optimization of a nonbiological atp binding protein for improved folding stability, Chem. Biol., 11, 865-874, (2004) [7] Chaslot, G., Saito, J.T., Bouzy, B., Uiterwijk, J., Van Den Herik, H.J.: Monte-carlo strategies for computer go. In: Proceedings of the 18th BeNeLux Conference on Artificial Intelligence, Namur, Belgium, pp. 83-91. Citeseer (2006) · Zbl 0404.90082 [8] Clarke, F.H.: Nonsmooth analysis and optimization. In: Proceedings of the International Congress of Mathematicians (Helsinki, 1978), pp. 847-853 (1983) · Zbl 0598.90075 [9] Cousty, J., Najman, L., Perret, B.: Constructive links between some morphological hierarchies on edge-weighted graphs. In: Mathematical Morphology and Its Applications to Signal and Image Processing, pp. 86-97. Springer (2013) · Zbl 1382.68291 [10] Csendes, T; Ratz, D, Subdivision direction selection in interval methods for global optimization, SIAM J. Numer. Anal., 34, 922-938, (1997) · Zbl 0873.65063 [11] Derbel, B., Preux, P.: Simultaneous optimistic optimization on the noiseless bbob testbed. In: IEEE Congress on Evolutionary Computation (CEC), pp. 2010-2017 (2015). doi:10.1109/CEC.2015.7257132 · Zbl 0742.90069 [12] Evtushenko, Y; Posypkin, M, A deterministic approach to global box-constrained optimization, Optim. Lett., 7, 819-829, (2013) · Zbl 1269.90082 [13] Evtushenko, YG, Numerical methods for finding global extrema (case of a non-uniform mesh), USSR Comput. Math. Math. Phys., 11, 38-54, (1971) · Zbl 0233.90007 [14] Evtushenko, YG; Malkova, V; Stanevichyus, A, Parallel global optimization of functions of several variables, Comput. Math. Math. Phys., 49, 246-260, (2009) · Zbl 1199.65197 [15] Finkel, D; Kelley, C, Additive scaling and the direct algorithm, J .Global Optim., 36, 597-608, (2006) · Zbl 1142.90488 [16] Finkel, D.E., Kelley, C.T.: Convergence analysis of the direct algorithm. NCSU Mathematics Department, Raleigh, NC (2004) · Zbl 1296.90090 [17] Floudas, C.A., Pardalos, P.M., Adjiman, C., Esposito, W.R., Gümüs, Z.H., Harding, S.T., Klepeis, J.L., Meyer, C.A., Schweiger, C.A.: Handbook of Test Problems in Local and Global Optimization, vol. 33. Springer Science & Business Media, Berlin (2013) · Zbl 0943.90001 [18] Fowkes, JM; Gould, NI; Farmer, CL, A branch and bound algorithm for the global optimization of Hessian Lipschitz continuous functions, J. Global Optim., 56, 1791-1815, (2013) · Zbl 1296.90090 [19] Gablonsky, J.: An implementation of the direct algorithm. Centre for Research in Scientific Computing, North Carolina State University, Tech. Rep. CRSC-TR98-29 (1998) · Zbl 1296.90090 [20] Gablonsky, J.: Modifications of the direct algorithm. Ph.D. thesis, North Carolina State University, Raleigh, North Carolina (2001) · Zbl 1039.90049 [21] Gablonsky, JM; Kelley, CT, A locally-biased form of the direct algorithm, J. Global Optim., 21, 27-37, (2001) · Zbl 1039.90049 [22] Hansen, N., Auger, A., Finck, S., Ros, R.: Real-parameter black-box optimization benchmarking 2012: Experimental setup. Tech. rep., INRIA (2012). http://coco.gforge.inria.fr/bbob2012-downloads [23] Hansen, N., Finck, S., Ros, R., Auger, A.: Real-parameter black-box optimization benchmarking 2009: Noiseless functions definitions. Tech. Rep. RR-6829, INRIA (2009). http://hal.inria.fr/inria-00362633/en/ · Zbl 1297.90130 [24] Hansen, P; Jaumard, B; Lu, SH, On the number of iterations of piyavskii’s global optimization algorithm, Math. Oper. Res., 16, 334-350, (1991) · Zbl 0742.90069 [25] Horst, R; Tuy, H, On the convergence of global methods in multiextremal optimization, J. Optim. Theory Appl., 54, 253-271, (1987) · Zbl 0595.90079 [26] Hu, J., Wang, Y., Zhou, E., Fu, M.C., Marcus, S.I.: A survey of some model-based methods for global optimization. In: Optimization, Control, and Applications of Stochastic Systems, pp. 157-179. Springer (2012) · Zbl 1374.90311 [27] Huyer, W; Neumaier, A, Global optimization by multilevel coordinate search, J. Global Optim., 14, 331-355, (1999) · Zbl 0956.90045 [28] Ivanov, V, On optimal algorithms of minimization in the class of functions with the Lipschitz condition, Inf. Process., 71, 1324-1327, (1972) [29] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181, (1993) · Zbl 0796.49032 [30] Kvasov, DE; Pizzuti, C; Sergeyev, YD, Local tuning and partition strategies for diagonal go methods, Numer. Math., 94, 93-106, (2003) · Zbl 1056.65059 [31] Kvasov, DE; Sergeyev, YD, Lipschitz gradients for global optimization in a one-point-based partitioning scheme, J. Comput. Appl. Math., 236, 4042-4054, (2012) · Zbl 1246.65091 [32] Kvasov, DE; Sergeyev, YD, Deterministic approaches for solving practical black-box global optimization problems, Adv. Eng. Softw., 80, 58-66, (2015) [33] Lai, TL; Robbins, H, Asymptotically efficient adaptive allocation rules, Adv. Appl. Math., 6, 4-22, (1985) · Zbl 0568.62074 [34] Laurence, A., Wolsey, G.L.N.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067 [35] Liu, Q; Cheng, W, A modified direct algorithm with bilevel partition, J. Global Optim., 60, 483-499, (2014) · Zbl 1303.90083 [36] Mayne, D; Polak, E, Outer approximation algorithm for nondifferentiable optimization problems, J. Optim. Theory Appl., 42, 19-30, (1984) · Zbl 0505.90068 [37] Mladineo, FH, An algorithm for finding the global maximum of a multimodal, multivariate function, Math. Prog., 34, 188-200, (1986) · Zbl 0598.90075 [38] Munos, R.: Optimistic optimization of a deterministic function without the knowledge of its smoothness. In: Advances in Neural Information Processing Systems, vol. 24, pp. 783-791. Curran Associates, Inc. (2011). http://papers.nips.cc/paper/4304-optimistic-optimization-of-a-deterministic-function-without-the-knowledge-of-its-smoothness.pdf [39] Paulavičius, R; Sergeyev, YD; Kvasov, DE; Žilinskas, J, Globally-biased DISIMPL algorithm for expensive global optimization, J. Global Optim., 59, 545-567, (2014) · Zbl 1297.90130 [40] Paulavičius, R., Žilinskas, J.: Simplicial Global Optimization. Springer, New York (2014) · Zbl 1401.90017 [41] Pintér, J.: Globally convergent methods for $$n$$-dimensional multiextremal optimization. Optimization 17(2), 187-202 (1986) · Zbl 0595.90071 [42] Pintér, J.: Global Optimization in Action: Continuous and Lipschitz Optimization: Algorithms, Implementations and Applications, vol. 6. Springer Science & Business Media, Berlin (1995) · Zbl 0842.90110 [43] Piyavskii, S, An algorithm for finding the absolute extremum of a function, USSR Comput. Math. Math. Phys., 12, 57-67, (1972) · Zbl 0249.65046 [44] Pošík, P.: Bbob-benchmarking the direct global optimization algorithm. In: GECCO ’09: Proceedings of the 11th annual conference companion on Genetic and evolutionary computation conference, pp. 2315-2320. ACM, New York, NY, USA (2009). doi:10.1145/1570256.1570323 [45] Pošík, P; Huyer, W; Pál, L, A comparison of global search algorithms for continuous black box optimization, Evolut. Comput., 20, 509-541, (2012) [46] Preux, P., Munos, R., Valko, M.: Bandits attack function optimization. In: IEEE Congress on Evolutionary Computation (CEC), pp. 2245-2252 (2014) [47] Ratz, D; Csendes, T, On the selection of subdivision directions in interval branch-and-bound methods for global optimization, J. Global Optim., 7, 183-207, (1995) · Zbl 0841.90116 [48] The Morgridge Institute for Research, I.M.: Bound constrained optimization. http://www.neos-guide.org/content/bound-constrained-optimization [49] Robbins, H; etal., Some aspects of the sequential design of experiments, Bull. Am. Math. Soc., 58, 527-535, (1952) · Zbl 0049.37009 [50] Roslund, J; Shir, OM; Bäck, T; Rabitz, H, Accelerated optimization and automated discovery with covariance matrix adaptation for experimental quantum control, Phys. Rev. A, 80, 043-415, (2009) [51] Sergeyev, YD, A one-dimensional deterministic global minimization algorithm, Comput. Math. Math. Phys., 35, 705-717, (1995) [52] Sergeyev, YD, On convergence of divide the best global optimization algorithms, Optimization, 44, 303-325, (1998) · Zbl 0986.90058 [53] 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 [54] Sergeyev, YD; Kvasov, DE, A deterministic global optimization using smooth diagonal auxiliary functions, Commun. Nonlinear Scie. Numer. Simul., 21, 99-111, (2015) · Zbl 1329.90112 [55] Sergeyev, YD; Strongin, RG, A global minimization algorithm with parallel iterations, USSR Comput. Math. Math. Phys., 29, 7-15, (1990) · Zbl 0702.65064 [56] Shubert, BO, A sequential method seeking the global maximum of a function, SIAM J. Numer. Anal., 9, 379-388, (1972) · Zbl 0251.65052 [57] Srinivas, N., Krause, A., Kakade, S.M., Seeger, M.: Gaussian process optimization in the bandit setting: no regret and experimental design. In: 27th International Conference on Machine Learning (2010) · Zbl 1365.94131 [58] Stover, C., Weisstein, E.W.: Hölder condition. MathWorld-A Wolfram Web Resource. http://mathworld.wolfram.com/HoelderCondition.html [59] Strongin, R.G.: Numerical methods in multi-extremal problems (information-statistical algorithms) (1978) · Zbl 0458.65062 [60] Strongin, RG, On the convergence of an algorithm for finding a global extremum, Eng. Cybernet., 11, 549-555, (1973) [61] Strongin, R.G., Sergeyev, Y.: Global Optimization and Non-Convex Constraints: Sequential and Parallel Algorithms. Kluwer Academic Publishers, Dordrecht (2000) · Zbl 0987.90068 [62] Strongin, RG; Sergeyev, YD, Global multidimensional optimization on parallel computer, Parallel Comput., 18, 1259-1273, (1992) · Zbl 0766.65052 [63] Sukharev, AG, Optimal strategies of the search for an extremum, USSR Comput. Math. Math. Phys., 11, 119-137, (1971) · Zbl 0255.90059 [64] Thompson, W.R.: On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, pp. 285-294 (1933) · JFM 59.1159.03 [65] Torn, A., Zilinskas, A.: Global Optimization. Springer, New York (1989) · Zbl 0752.90075 [66] Valko, M., Carpentier, A., Munos, R.: Stochastic simultaneous optimistic optimization. In: Proceedings of the 30th International Conference on Machine Learning (ICML-13), pp. 19-27 (2013) · Zbl 0986.90058 [67] Wang, Z., Shakibi, B., Jin, L., de Freitas, N.: Bayesian multi-scale optimistic optimization. In: Proceedings of International Conference on Artificial Intelligence and Statistics (AISTATS 2014), pp. 1005-1014 (2014) · Zbl 0505.90068
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.