Abstract
We propose some strategies that can be shown to improve the performance of the radial basis function (RBF) method by Gutmann [J. Global optim. 19(3), 201–227 (2001a)] (Gutmann-RBF) and the RBF method by Regis and Shoemaker [J. Global optim. 31, 153–171 (2005)] (CORS–RBF) on some test problems when they are initialized by symmetric Latin hypercube designs (SLHDs). Both methods are designed for the global optimization of computationally expensive functions with multiple local optima. We demonstrate how the original implementation of Gutmann-RBF can sometimes converge slowly to the global minimum on some test problems because of its failure to do local search. We then propose Controlled Gutmann-RBF (CG-RBF), which is a modification of Gutmann-RBF where the function evaluation point in each iteration is restricted to a subregion of the domain centered around a global minimizer of the current RBF model. By varying the size of this subregion in different iterations, we ensure a better balance between local and global search. Moreover, we propose a complete restart strategy for CG-RBF and CORS-RBF whenever the algorithm fails to make any substantial progress after some threshold number of consecutive iterations. Computational experiments on the seven Dixon and Szegö [Towards Global optimization, pp. 1–13. North-Holland, Amsterdam (1978)] test problems and on nine Schoen [J. Global optim. 3, 133–137 (1993)] test problems indicate that the proposed strategies yield significantly better performance on some problems. The results also indicate that, for some fixed setting of the restart parameters, the two modified RBF algorithms, namely CG-RBF-Restart and CORS-RBF-Restart, are comparable on the test problems considered. Finally, we examine the sensitivity of CG-RBF-Restart and CORS-RBF-Restart to the restart parameters.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Björkman M., Holmström K. (2000). Global optimization of costly nonconvex functions using radial basis functions. Optim. Eng. 1(4):373–397
Booker A.J., Dennis J.E., Frank P.D., Serafini D.B., Torczon V., Trosset M.W. (1999). A rigorous framework for optimization of expensive functions by surrogates. Struct. Optim. 17(1):1–13
Buhmann M.D. (2003). Radial Basis Functions. Cambridge University Press, UK
Conn A.R., Scheinberg K., Toint Ph.L. (1997) Recent progress in unconstrained nonlinear optimization without derivatives. Math. Program. 79(3):397–414
Dixon L.C.W., Szegö G. (1978). The global optimization problem: an introduction. In: Dixon L.C.W., Szegö G. (eds) Towards Global Optimization 2. North-Holland, Amsterdam, pp. 1–15
Gomes C.P., Selman B., Crato N., Kautz H. (2000). Heavy-tailed phenomena in satisfiability and constraint satisfaction problems. J. Automated Reasoning 24:67–100
Gutmann H.-M. (2001a). A radial basis function method for global optimization. J. Global Optim. 19(3):201–227
Gutmann H.-M. (2001b). Radial basis function methods for global optimization. PhD Thesis, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, UK
Holmström K. (1999). The TOMLAB optimization environment in Matlab. Adv. Model. Optim. 1(1):47–69
Horst R., Pardalos P.M., Thoai N.V. (2000). Introduction to Global Optimization, 2nd Edn. Kluwer, Dordrecht
Jones, D.R.: Global Optimization with Response Surfaces, presented at the Fifth SIAM Conference on Optimization, Victoria, Canada (1996).
Jones D.R., Perttunen C.D., Stuckman B.E. (1993). Lipschitz optimization without the lipschitz constant. J. Optim. Theor. Appli. 78(1):157–181
Jones D.R., Schonlau M., Welch W.J. (1998). Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4):455–492
Marazzi M., Nocedal J. (2002). Wedge trust region methods for derivative free optimization. Math. Program. Ser. A 91:289–305
McKay M., Beckman R., Conover W. (1979). A Comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics 21:239–246
Powell, M.J.D.: The theory of radial basis function approximation in 1990. In: Light, W. (ed.) Advances in Numerical Analysis, Vol. 2, Wavelets, Subdivision Algorithms and Radial Basis Functions, pp. 105–210. Oxford University Press, (1992)
Powell M.J.D. (1996). A review of algorithms for thin plate spline interpolation in two dimensions. In: Fontanella F., Jetter K., Laurent P.J. (eds) Advanced Topics in Multivariate Approximation. World Scientific Publishing, River Edge, NJ, pp. 303–322
Powell M.J.D. (1999). Recent research at cambridge on radial basis functions. In: Müller M., Buhmann M., Mache D. and Felten M. (eds) New Developments in Approximation Theory. International Series of Numerical Mathematics, Vol. 132, Birkhauser Verlag, Basel, pp. 215–232
Powell M.J.D. (2000). UOBYQA: unconstrained optimization by quadratic approximation. Math. Program. 92:555–582
Powell M.J.D. (2002). On trust region methods for unconstrained minimization without derivatives. Math. Program. 97:605–623
Regis R.G., Shoemaker C.A. (2005). Constrained global optimization using radial basis functions. J. Global Optim. 31:153–171
Rinnooy Kan A.H.G., Timmer G.T. (1987). Stochastic global optimization methods, part II: multi level methods. Math. Program. 39:57–78
Serafini, D.B.: A framework for managing models in non-linear optimization of computationally expensive functions. Ph.D. Thesis, Department of Computational and Applied Mathematics, Rice (1998)
Schoen F. (1993). A wide class of test functions for global optimization. J. Global Optim. 3:133–137
The Mathworks Inc. Optimization Toolbox for use with MATLAB: User’s Guide, Version 3, Natick, MA (2004)
Torczon V. (1997). On the convergence of pattern search algorithms. SIAM J. Optim. 7(1):1–25
Torn A., Zilinskas A. (1989). Global Optimization. Lecture Notes in Computer Science, Vol. 350, Springer-Verlag, Berlin
Ye K.Q., Li W., Sudjianto A. (2000). Algorithmic construction of optimal symmetric latin hypercube designs. J. Stat. Plan. Infer. 90:145–159
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Regis, R.G., Shoemaker, C.A. Improved Strategies for Radial basis Function Methods for Global Optimization. J Glob Optim 37, 113–135 (2007). https://doi.org/10.1007/s10898-006-9040-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-006-9040-1