Global optimization via inverse distance weighting and radial basis functions. (English) Zbl 1466.90075

Summary: Global optimization problems whose objective function is expensive to evaluate can be solved effectively by recursively fitting a surrogate function to function samples and minimizing an acquisition function to generate new samples. The acquisition step trades off between seeking for a new optimization vector where the surrogate is minimum (exploitation of the surrogate) and looking for regions of the feasible space that have not yet been visited and that may potentially contain better values of the objective function (exploration of the feasible space). This paper proposes a new global optimization algorithm that uses inverse distance weighting (IDW) and radial basis functions (RBF) to construct the acquisition function. Rather arbitrary constraints that are simple to evaluate can be easily taken into account. Compared to Bayesian optimization, the proposed algorithm, that we call GLIS (GLobal minimum using Inverse distance weighting and Surrogate radial basis functions), is competitive and computationally lighter, as we show in a set of benchmark global optimization and hyperparameter tuning problems. MATLAB and Python implementations of GLIS are available at http://cse.lab.imtlucca.it/~bemporad/glis.


90C26 Nonconvex programming, global optimization
Full Text: DOI arXiv


[1] Banjac, G., Stellato, B., Moehle, N., Goulart, P., Bemporad, A., Boyd, S.: Embedded code generation using the OSQP solver. In: Proc. 56th IEEE Conf. on Decision and Control, pp. 1906-1911, Melbourne, Australia, 2017. https://github.com/oxfordcontrol/osqp
[2] Bemporad, A.: Model-based predictive control design: new trends and tools. In: Proc. 45th IEEE Conf. on Decision and Control, pp. 6678-6683, San Diego, CA (2006)
[3] Bemporad, A., A multiparametric quadratic programming algorithm with polyhedral computations based on nonnegative least squares, IEEE Trans. Autom. Control, 60, 11, 2892-2903 (2015) · Zbl 1360.90181
[4] Bemporad, A.: Global optimization via inverse distance weighting. 2019. Available on arXiv at arxiv:1906.06498. Code available at http://cse.lab.imtlucca.it/ bemporad/glis
[5] Bemporad, A., Piga, D.: Active preference learning based on radial basis functions. 2019. Available on arXiv at arxiv:1909.13049. Code available at http://cse.lab.imtlucca.it/ bemporad/idwgopt
[6] Blok, H.J.: The lhsdesigncon MATLAB function, 2014. https://github.com/rikblok/matlab-lhsdesigncon
[7] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1, 1-122 (2011) · Zbl 1229.90122
[8] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, New York, NY, USA (2004). http://www.stanford.edu/ boyd/cvxbook.html · Zbl 1058.90049
[9] Brochu, E., Cora, V.M., De Freitas, N.: A tutorial on Bayesian optimization of expensive cost functions, with application to active user modeling and hierarchical reinforcement learning. arXiv preprintarXiv:1012.2599 (2010)
[10] Cimini, G., Bemporad, A., Bernardini, D.: ODYS QP Solver. ODYS S.r.l. (https://odys.it/qp), September 2017
[11] Costa, A.; Nannicini, G., Rbfopt: an open-source library for black-box optimization with costly function evaluations, Math. Program. Comput., 10, 4, 597-629 (2018) · Zbl 1411.90005
[12] Eberhart, R., Kennedy, J.: A new optimizer using particle swarm theory. In: Proceedings of the Sixth International Symposium on Micro Machine and Human Science, pp. 39-43. Nagoya (1995)
[13] Feurer, M., Klein, A., Eggensperger, K., Springenberg, J.T., Blum, M., Hutter, F.: Auto-sklearn: efficient and robust automated machine learning. In: Hutter, F., Kotthoff, L., Vanschoren, J. (eds.) Automated Machine Learning: Methods, Systems, Challenges, pp. 113-134. Springer International Publishing (2019)
[14] Forgione, M., Piga, D., Bemporad, A.: Efficient calibration of embedded MPC. In: Proc. 21th IFAC World Congress. https://arxiv.org/abs/1911.13021 (2020)
[15] Gutmann, H-M, A radial basis function method for global optimization, J. Glob. Optim., 19, 201-2227 (2001) · Zbl 0972.90055
[16] Hansen, N.; Ostermeier, A., Completely derandomized self-adaptation in evolution strategies, Evol. Comput., 9, 2, 159-195 (2001)
[17] Hardy, RL, Multiquadric equations of topography and other irregular surfaces, J. Geophys. Res., 76, 8, 1905-1915 (1971)
[18] Huyer, W.; Neumaier, A., Global optimization by multilevel coordinate search, J. Glob. Optim., 14, 4, 331-355 (1999) · Zbl 0956.90045
[19] Jamil, M., Yang, X.-S.: A literature survey of benchmark functions for global optimisation problems. Int. J. Math. Model. Numer. Optim. 4(2):150-194 (2013). arxiv:1308.4008.pdf · Zbl 1280.65053
[20] Johnson, S.G.: The NLopt nonlinear-optimization package. http://github.com/stevengj/nlopt
[21] Jones, DR, A taxonomy of global optimization methods based on response surfaces, J. Glob. Optim., 21, 4, 345-383 (2001) · Zbl 1172.90492
[22] Jones, D.R.: DIRECT global optimization algorithm. Encyclopedia of Optimization, pages 725-735, (2009)
[23] Jones, DR; Schonlau, M.; Matthias, WJ, Efficient global optimization of expensive black-box functions, J. Glob. Optim., 13, 4, 455-492 (1998) · Zbl 0917.90270
[24] Joseph, VR; Kang, L., Regression-based inverse distance weighting with applications to computer experiments, Technometrics, 53, 3, 255-265 (2011)
[25] Kushner, HJ, A new method of locating the maximum point of an arbitrary multipeak curve in the presence of noise, J. Basic Eng., 86, 1, 97-106 (1964)
[26] Matheron, G., Principles of geostatistics, Econ. Geol., 58, 8, 1246-1266 (1963)
[27] McDonald, DB; Grantham, WJ; Tabor, WL; Murphy, MJ, Global and local optimization using radial basis function response surface models, Appl. Math. Model., 31, 10, 2095-2110 (2007) · Zbl 1162.90562
[28] McKay, MD; Beckman, RJ; Conover, WJ, Comparison of three methods for selecting values of input variables in the analysis of output from a computer code, Technometrics, 21, 2, 239-245 (1979) · Zbl 0415.62011
[29] Piga, D., Forgione, M., Formentin, S., Bemporad, A.: Performance-oriented model learning for data-driven MPC design. IEEE Control Systems Letters, 2019. Also in Proc. 58th IEEE Conf. Decision and Control, Nice (France) (2019). arxiv:1904.10839
[30] Powell, M.J.D.: The NEWUOA software for unconstrained optimization without derivatives. In Large-scale nonlinear optimization, pp. 255-297. Springer (2006) · Zbl 1108.90005
[31] Regis, RG; Shoemaker, CA, Constrained global optimization of expensive black box functions using radial basis functions, J. Glob. Optim., 31, 1, 153-171 (2005) · Zbl 1274.90511
[32] Rios, LM; Sahinidis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Glob. Optim., 56, 3, 1247-1293 (2013) · Zbl 1272.90116
[33] Rippa, S., An algorithm for selecting a good value for the parameter c in radial basis function interpolation, Adv. Comput. Math., 11, 2-3, 193-210 (1999) · Zbl 0943.65017
[34] Sacks, J., Welch, W.J., Mitchell, T.J., Wynn, H.P.: Design and analysis of computer experiments. Stat. Sci. 409-423 (1989) · Zbl 0955.62619
[35] Shahriari, B.; Swersky, K.; Wang, Z.; Adams, RP; De Freitas, N., Taking the human out of the loop: a review of Bayesian optimization, Proc. IEEE, 104, 1, 148-175 (2015)
[36] Shepard, D.: A two-dimensional interpolation function for irregularly-spaced data. In: Proc. ACM National Conference, pp. 517-524. New York (1968)
[37] Snoek, J., Jasper, H., Adams, R.P.: Practical Bayesian optimization of machine learning algorithms. In: Advances in Neural Information Processing Systems, pp. 2951-2959 (2012)
[38] The GPyOpt authors. GPyOpt: a Bayesian optimization framework in Python. http://github.com/SheffieldML/GPyOpt (2016)
[39] The Mathworks, Inc. Statistics and Machine Learning Toolbox User’s Guide (2019). https://www.mathworks.com/help/releases/R2019a/pdf_doc/stats/stats.pdf
[40] Törn, A.; Žilinskas, A., Global Optimization (1989), Berlin: Springer, Berlin · Zbl 0752.90075
[41] Vaz, AIF; Vicente, LN, A particle swarm pattern search method for bound constrained global optimization, J. Glob. Optim., 39, 2, 197-219 (2007) · Zbl 1180.90252
[42] Vaz, A.I.F., Vicente, L.N.: PSwarm: a hybrid solver for linearly constrained global derivative-free optimization. Optim. Methods Softw. 24, 669-685 (2009). http://www.norg.uminho.pt/aivaz/pswarm/ · Zbl 1177.90327
[43] Whitley, D., A genetic algorithm tutorial, Stat. Comput., 4, 2, 65-85 (1994)
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.