Constrained global optimization of expensive black box functions using radial basis functions. (English) Zbl 1274.90511

Summary: We present a new strategy for the constrained global optimization of expensive black box functions using response surface models. A response surface model is simply a multivariate approximation of a continuous black box function which is used as a surrogate model for optimization in situations where function evaluations are computationally expensive. Prior global optimization methods that utilize response surface models were limited to box-constrained problems, but the new method can easily incorporate general nonlinear constraints. In the proposed method, which we refer to as the Constrained Optimization using Response Surfaces (CORS) Method, the next point for costly function evaluation is chosen to be the one that minimizes the current response surface model subject to the given constraints and to additional constraints that the point be of some distance from previously evaluated points. The distance requirement is allowed to cycle, starting from a high value (global search) and ending with a low value (local search). The purpose of the constraint is to drive the method towards unexplored regions of the domain and to prevent the premature convergence of the method to some point which may not even be a local minimizer of the black box function. The new method can be shown to converge to the global minimizer of any continuous function on a compact set regardless of the response surface model that is used. Finally, we considered two particular implementations of the CORS method which utilize a radial basis function model (CORS-RBF) and applied it on the box-constrained Dixon \(-\) Szegö test functions and on a simple nonlinearly constrained test function. The results indicate that the CORS-RBF algorithms are competitive with existing global optimization algorithms for costly functions on the box-constrained test problems. The results also show that the CORS-RBF algorithms are better than other algorithms for constrained global optimization on the nonlinearly constrained test problem.


90C59 Approximation methods and heuristics in mathematical programming
90C30 Nonlinear programming
Full Text: DOI


[1] Björkman, M.; Holmström, K., Global optimization of costly nonconvex functions using radial basis functions, Optimization Engineering, 1, 373-397, (2000) · Zbl 1035.90061
[2] Booker, A.J.; Dennis, J.E.; Frank, P.D.; Serafini, D.B.; Torczon, V.; Trosset, M.W., A rigorous framework for optimization of expensive functions by surrogates, Structural Optimization, 17, 1-13, (1999)
[3] Box, G.E.P.; Draper, N.R., (1987), New York · Zbl 0614.62104
[4] Cressie, N., (1993), New York
[5] Dennis, J.E.; Torczon, V., Direct search methods on parallel machines, SIAM Journal on Optimization, 1, 448-474, (1991) · Zbl 0754.90051
[6] Dixon, L.C.W. and Szegö, G. (1978), The global optimization problem: an introduction. In: Dixon, L.C.W. and Szegö, G. (eds.), Towards Global Optimization 2, pp. 1-15, North-Holland, Amsterdam.
[7] Friedman, J.H., Multivariate adaptive regression splines (with discussion), Annals of Statistics, 19, 1-141, (1991) · Zbl 0765.62064
[8] Gomez, S. and Levy, A. (1982), The tunneling method for solving the constrained global optimization problem with several non-connected feasible regions. In: Dold, A. and Eckmann, B. (eds.), Numerical Analysis, Lecture Notes in Mathematics 909, pp. 34-47, Springer-Verlag. · Zbl 0473.65038
[9] Gutmann, H.-M. (2001a), Radial basis function methods for global optimization. Ph.D. Thesis, University of Cambridge. · Zbl 0972.90055
[10] Gutmann, H.-M., A radial basis function method for global optimization, Journal of Global Optimization, 19, 201-227, (2001) · Zbl 0972.90055
[11] Homström, K., The TOMLAB optimization environment in Matlab, Advanced Modeling and Optimization, 1, 47-69, (1999) · Zbl 1115.90404
[12] Horst, R.; Pardalos, P.M.; Thoai, N.V., (1995), New York · Zbl 0836.90134
[13] Ishikawa, T.; Matsunami, M., An optimization method based on radial basis functions, IEEE Transactions on Magnetics, 33, 1868-1871, (1997)
[14] Ishikawa, T.; Tsukui, Y.; Matsunami, M., A combined method for the global optimization using radial basis function and deterministic approach, IEEE Transactions on Magnetics, 35, 1730-1733, (1999)
[15] Jones, D.R. (1996), Global optimization with response surfaces, presented at the Fifth SIAM Conference on Optimization, Victoria, Canada.
[16] Jones, D.R., A taxonomy of global optimization methods based on response surfaces, Journal of Global Optimization, 21, 345-383, (2001a) · Zbl 1172.90492
[17] Jones, D.R. (2001b), The DIRECT global optimization algorithm. In: Floudas, C.A. and Pardalos, P.M. (eds.), Encyclopedia of Optimization, Vol. 1, pp. 431-440. Kluwer Academic Publishers
[18] Jones, D.R.; Perttunen, C.D.; Stuckman, B.E., Lipschitz optimization without the Lipschitz constant, Journal of Optimization Theory and Applications, 78, 157-181, (1993) · Zbl 0796.49032
[19] Jones, D.R.; Schonlau, M.; Welch, W.J., Efficient global optimization of expensive black-box functions, Journal of Global Optimization, 13, 455-492, (1998) · Zbl 0917.90270
[20] Khuri, A.I.; Cornell, J.A., (1987), New York · Zbl 0632.62069
[21] Koehler, J.R. and Owen, A.B. (1996), Computer experiments. In: Ghosh, S. and Rao, C.R. (eds.), Handbook of Statistics, 13: Design and Analysis of Computer Experiments, pp. 261-308. North-Holland, Amsterdam. · Zbl 0919.62089
[22] McKay, M.; Beckman, R.; Conover, W., A comparison of three methods for selecting values of input variables in the analysis of output from a computer code, Technometrics, 21, 239-246, (1979) · Zbl 0415.62011
[23] Myers, R.H.; Montgomery, D.C., (1995), New York · Zbl 1161.62392
[24] Nelder, J.A.; Mead, R., A simplex method for function minimization, Computer Journal, 7, 308-313, (1965) · Zbl 0229.65053
[25] Nocedal, J.; Wright, S.J., (1999), New York · Zbl 0930.65067
[26] Powell, M.J.D. (1992), The theory of Radial Basis Function Approximation in 1990, in: Light, W. (ed.), Advances in Numerical Analysis, Volume 2: Wavelets, Subdivision Algorithms and Radial Basis Functions, pp. 105-210. Oxford University Press.
[27] Powell, M.J.D.; Gomez, S. (ed.); Hennart, J.-P. (ed.), A direct search optimization method that models the objective and constraint functions by linear interpolation, 51-67, (1994), New York · Zbl 0826.90108
[28] Powell, M.J.D.; Müller, M. (ed.); Buhmann, M. (ed.); Mache, D. (ed.); Felten, M. (ed.), Recent research at Cambridge on radial basis functions, 215-232, (1999), Basel · Zbl 0958.41501
[29] Powell, M.J.D., UOBYQA: unconstrained optimization by quadratic approximation, Mathematical Programming, 92, 555-582, (2000) · Zbl 1014.65050
[30] Powell, M.J.D., (2002), UK.
[31] Sacks, J.; Welch, W.J.; Mitchell, T.J.; Wynn, H.P., Design and analysis of computer experiments, Statistical Science, 4, 409-435, (1989) · Zbl 0955.62619
[32] Simpson, T.W., Mauery, T.M., Korte, J.J. and Mistree, F. (1998), Comparison of response surface and kriging models for multidisciplinary design optimization. In: Proceedings of the 7th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, Vol. 1, pp. 381-391. St. Louis, MO.
[33] The Mathworks, Inc. (2000), Optimization Toolbox for use with MATLAB: User’s Guide, Version 2.1.
[34] Torczon, V., No article title, On the convergence of pattern search algorithms, SIAM Journal on Optimization, 7, 1-25, (1997) · Zbl 0884.65053
[35] Torn, A.; Zilinskas, A., (1989), Berlin
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.