×

zbMATH — the first resource for mathematics

RBFOpt: an open-source library for black-box optimization with costly function evaluations. (English) Zbl 1411.90005
Summary: We consider the problem of optimizing an unknown function given as an oracle over a mixed-integer box-constrained set. We assume that the oracle is expensive to evaluate, so that estimating partial derivatives by finite differences is impractical. In the literature, this is typically called a black-box optimization problem with costly evaluation. This paper describes the solution methodology implemented in the open-source library RBFOpt, available on COIN-OR. The algorithm is based on the Radial Basis Function method originally proposed by H. M. Gutmann [J. Glob. Optim. 19, No. 3, 201–227 (2001; Zbl 0972.90055)], which builds and iteratively refines a surrogate model of the unknown objective function. The two main methodological contributions of this paper are an approach to exploit a noisy but less expensive oracle to accelerate convergence to the optimum of the exact oracle, and the introduction of an automatic model selection phase during the optimization process. Numerical experiments show that RBFOpt is highly competitive on a test set of continuous and mixed-integer nonlinear unconstrained problems taken from the literature: it outperforms the open-source solvers included in our comparison by a large amount, and performs slightly better than a commercial solver. Our empirical evaluation provides insight on which parameterizations of the algorithm are the most effective in practice. The software reviewed as part of this submission was given the Digital Object Identifier (DOI) doi:10.5281/zenodo.597767.

MSC:
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90C56 Derivative-free methods and methods using generalized derivatives
90C30 Nonlinear programming
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Achterberg, T., SCIP: solving constraint integer programs, Math. Program. Comput., 1, 1-41, (2009) · Zbl 1171.90476
[2] Audet, C.; Dennis, J., Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 188-217, (2004) · Zbl 1112.90078
[3] Audet, C.; Kokkolaras, M.; Digabel, S.; Talgorn, B., Order-based error for managing ensembles of surrogates in mesh adaptive direct search, J. Glob. Optim., 70, 645-675, (2018) · Zbl 1394.90525
[4] Baudoui, V.: Optimisation robuste multiobjectifs par modèles de substitution. Ph.D. thesis, University of Toulouse Paul Sabatier (2012)
[5] Björkman, M.; Holmström, K., Global optimization of costly nonconvex functions using radial basis functions, Optim. Eng., 1, 373-397, (2000) · Zbl 1035.90061
[6] Bonami, P.; Biegler, L.; Conn, A.; Cornuéjols, G.; Grossmann, I.; Laird, C.; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 186-204, (2008) · Zbl 1151.90028
[7] Bussieck, MR; Drud, AS; Meeraus, A., MINLPLib—a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 114-119, (2003) · Zbl 1238.90104
[8] Byrd, RH; Nocedal, J.; Waltz, RA; Pillo, G. (ed.); Roma, M. (ed.), KNITRO: an integrated package for nonlinear optimization, 35-59, (2006), New York · Zbl 1108.90004
[9] Conn, AR; Scheinberg, K.; Toint, PL, Recent progress in unconstrained nonlinear optimization without derivatives, Math. Program., 79, 397-414, (1997) · Zbl 0887.90154
[10] Conn, A.R., Scheinberg, K., Vicente, L.N.: Introduction to Derivative-Free Optimization. MPS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics, Philadelphia (2009) · Zbl 1163.49001
[11] Costa, A.; Buccio, E.; Melucci, M.; Nannicini, G., Efficient parameter estimation for information retrieval using black-box optimization, IEEE Trans. Knowl. Data Eng., 30, 1240-1253, (2017)
[12] Costa, Alberto; Nannicini, Giacomo; Schroepfer, Thomas; Wortmann, Thomas, Black-Box Optimization of Lighting Simulation in Architectural Design, 27-39, (2015), Cham
[13] D’Ambrosio, C.; Nannicini, G.; Sartor, G., MILP models for the selection of a small set of well-distributed points, Oper. Res. Lett., 45, 46-52, (2017) · Zbl 1409.90113
[14] Diaz, GI; Fokour, A.; Nannicini, G.; Samulowitz, H., An effective algorithm for hyperparameter optimization of neural networks, IBM J. Res. Dev., 61, 9-1, (2017)
[15] Dixon, L.; Szego, G.; Dixon, L. (ed.); Szego, G. (ed.), The global optimization problem: an introduction, 1-15, (1975), Amsterdam
[16] Eriksson, D., Bindel, D., Shoemaker, C.: Surrogate optimization toolbox (pySOT) (2015). http://github.com/dme65/pySOT
[17] Fuerle, F.; Sienz, J., Formulation of the Audze-Eglais uniform latin hypercube design of experiments for constrained design spaces, Adv. Eng. Softw., 42, 680-689, (2011) · Zbl 1416.62449
[18] Gablonsky, J.; Kelley, C., A locally-biased form of the DIRECT algorithm, J. Glob. Optim., 21, 27-37, (2001) · Zbl 1039.90049
[19] Gendreau, M., Potvin, J.Y. (eds.): Handbook of Metaheuristics, 2nd edn. Kluwer, Dordrecht (2010) · Zbl 1198.90002
[20] Glover, F., Kochenberger, G. (eds.): Handbook of Metaheuristics. Kluwer, Dordrecht (2003) · Zbl 1058.90002
[21] Gomes, CP; Selman, B.; Crato, N.; Kautz, H., Heavy-tailed phenomena in satisfiability and constraint satisfaction problems, J. Autom. Reason., 24, 67-100, (2000) · Zbl 0967.68145
[22] Gutmann, HM, A radial basis function method for global optimization, J. Glob. Optim., 19, 201-227, (2001) · Zbl 0972.90055
[23] Hart, W.E., Laird, C., Watson, J.P., Woodruff, D.L.: Pyomo—optimization Modeling in Python. Springer Optimization and Its Applications, vol. 67. Springer, Berlin (2012) · Zbl 1233.90002
[24] Hart, WE; Watson, JP; Woodruff, DL, Pyomo: modeling and solving mathematical programs in Python, Math. Program. Comput., 3, 219-260, (2011)
[25] Hemker, T.: Derivative free surrogate optimization for mixed-integer nonlinear black-box problems in engineering. Master’s thesis, Technischen Universität Darmstadt (2008)
[26] Holmström, K., An adaptive radial basis algorithm (ARBF) for expensive black-box global optimization, J. Glob. Optim., 41, 447-464, (2008) · Zbl 1152.90609
[27] Holmström, K.; Quttineh, NH; Edvall, MM, An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer constrained global optimization, Optim. Eng., 9, 311-339, (2008) · Zbl 1400.90226
[28] Huyer, W.; Neumaier, A., SNOBFIT—stable noisy optimization by branch and fit, ACM Trans. Math. Softw., 35, 1-25, (2008)
[29] Ilievski, I., Akhtar, T., Feng, J., Shoemaker, C.A.: Efficient hyperparameter optimization of deep learning algorithms using deterministic RBF surrogates. In: Thirty-First AAAI Conference on Artificial Intelligence (2017)
[30] Jakobsson, S.; Patriksson, M.; Rudholm, J.; Wojciechowski, A., A method for simulation based optimization using radial basis functions, Optim. Eng., 11, 501-532, (2010) · Zbl 1243.65068
[31] Johnson, S.G.: The NLopt nonlinear-optimization package. http://ab-initio.mit.edu/nlopt
[32] Jones, D.; Perttunen, C.; Stuckman, B., Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181, (1993) · Zbl 0796.49032
[33] Jones, D.; Schonlau, M.; Welch, W., Efficient global optimization of expensive black-box functions, J. Glob. Optim., 13, 455-492, (1998) · Zbl 0917.90270
[34] Kolda, TG; Lewis, RM; Torczon, VJ, Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev., 45, 385-482, (2003) · Zbl 1059.90146
[35] Digabel, S., Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm, ACM Trans. Math. Softw., 37, 44:1-44:15, (2011) · Zbl 1365.65172
[36] MINLP Library 2. http://www.gamsworld.org/minlp/minlplib2/html/
[37] Moré, J.; Wild, SM, Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 172-191, (2009) · Zbl 1187.90319
[38] Müller, Juliane, MISO: mixed-integer surrogate optimization framework, Optimization and Engineering, 17, 177-203, (2015) · Zbl 1364.90230
[39] Müller, J.; Paudel, R.; Shoemaker, CA; Woodbury, J.; Wang, Y.; Mahowald, N., \(\text{CH}_{4}\) parameter estimation in CLM4.5bgc using surrogate global optimization, Geosci. Model Dev., 8, 3285-3310, (2015)
[40] Müller, J.; Shoemaker, CA, Influence of ensemble surrogate models and sampling strategy on the solution quality of algorithms forcomputationally expensive black-box global optimization problems, J. Glob. Optim., 60, 123-144, (2014) · Zbl 1312.90064
[41] Müller, J.; Shoemaker, CA; Piché, R., SO-MI: a surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems, Comput. Oper. Res., 40, 1383-1400, (2013) · Zbl 1352.90067
[42] Nelder, JA; Mead, R., A simplex method for function minimization, Comput. J., 7, 308-313, (1965) · Zbl 0229.65053
[43] Neumaier, A.: Neumaier’s collection of test problems for global optimization. http://www.mat.univie.ac.at/ neum/glopt/my_problems.html. Retrieved in May 2014
[44] Powell, M. J. D., Recent research at Cambridge on radial basis functions, 215-232, (1999), Basel · Zbl 0958.41501
[45] Powell, M.J.: The BOBYQA algorithm for bound constrained optimization without derivatives. Technical Report, Cambridge NA Report NA2009/06, University of Cambridge (2009)
[46] Regis, R.; Shoemaker, C., Improved strategies for radial basis function methods for global optimization, J. Glob. Optim., 37, 113-135, (2007) · Zbl 1149.90120
[47] Regis, RG; Shoemaker, CA, A stochastic radial basis function method for the global optimization of expensive functions, INFORMS J. Comput., 19, 497-509, (2007) · Zbl 1241.90192
[48] Regis, RG; Shoemaker, CA, A quasi-multistart framework for global optimization of expensive functions using response surface models, J. Glob. Optim., 56, 1719-1753, (2013) · Zbl 1275.90068
[49] 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
[50] Schoen, F., A wide class of test functions for global optimization, J. Glob. Optim., 3, 133-137, (1993) · Zbl 0772.90072
[51] Törn, A., Žilinskas, A.: Global Optimization. Springer, Berlin (1987) · Zbl 0752.90075
[52] Wächter, A.; Biegler, LT, On the implementation of a primal-dual interior point filter line search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57, (2006) · Zbl 1134.90542
[53] Wortmann, T.; Costa, A.; Nannicini, G.; Schroepfer, T., Advantages of surrogate models for architectural design optimization, Artif. Intell. Eng. Des. Anal. Manuf., 29, 471-481, (2015)
[54] Wortmann, T., Waibel, C., Nannicini, G., Evins, R., Schroepfer, T., Carmeliet, J.: Are genetic algorithms really the best choice for building energy optimization? In: Proceedings of the Symposium on Simulation for Architecture & Urban Design (SimAUD), pp. 51-58. SCS, Toronto, Canada (2017)
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.