Evaluation of a Surrogate Based Method for Global Optimization

Authors: David Lindström

Abstract:

We evaluate the performance of a numerical method for global optimization of expensive functions. The method is using a response surface to guide the search for the global optimum. This metamodel could be based on radial basis functions, kriging, or a combination of different models. We discuss how to set the cyclic parameters of the optimization method to get a balance between local and global search. We also discuss the eventual problem with Runge oscillations in the response surface.

Keywords: Expensive function, infill sampling criterion, kriging, global optimization, response surface, Runge phenomenon.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1105751

References:

[1] D. Lindström, and K. Eriksson, “A Surrogate Based Global Optimization Method”, Proceedings of the 38th CIE Conference, Beijing, China, 2008.
[2] J. A. Nelder, R. Mead, "A simple method for function minimization", Computer Journal, 7, 1965, pp. 308–313.
[3] D. R. Jones, C. D. Perttunen, and B. E. Stuckmann, “Lipschitzian optimization without the Lipschitz constant”, Journal of Optimization Theory and Applications, 79, 1993, pp. 157-181.
[4] R. L. Haupt, and S. E. Haupt, “Practical genetic algorithms”, 2nd ed., Wiley, 2004.
[5] C. Blum, and A. Roli, “Metaheuristics in combinatorial optimization: overview and conceptual comparison”, ACM Computing Surveys, 35 (3), 2003, pp. 268–308.
[6] R. H. Myers, D. C. and Montgomery, “Response surface methodology: process and product optimization using designed experiments”, 2nd ed., Wiley, 2002.
[7] D. R. Jones, M. Schonlau, and W. J. Welch, “Efficient global optimization of expensive black-box functions”, Journal of Global Optimization 13(4), 1998, pp. 455-492.
[8] D. R. Jones, “A taxonomy of global optimization methods based on response surfaces”, Journal of Global Optimization 21, 2001, pp. 345- 383.
[9] D. den Hertog, J. P. C. Kleijnen, and A. Y. D. Siem, “The correct kriging variance estimated by bootstrapping”, Journal of the Operational Research Society, Vol. 57, No. 4, 2006, pp. 400–409.
[10] J. P. C. Kleijnen, W. van Beers, and I. van Nieuwenhuyse, “Expected Improvement in efficient global optimization through bootstrapped kriging”, Journal of Global Optimization, 2011.
[11] H.-M. Gutmann, “A radial basis function method for global optimization”, Journal of Global Optimization 19, 2001, pp. 201-227.
[12] R. G. Regis, and C. A. Shoemaker, “Improved strategies for radial basis function methods for global optimization”, Journal of Global Optimization, Vol. 37, 2007, pp. 113-135.
[13] R. G. Regis and C. A. Shoemaker, “A stochastic radial basis function method for the global optimization of expensive functions”, INFORMS Journal on Computing, Vol. 19, Issue 4, 2007, pp. 497–509.
[14] S. Jakobsson, M. Patriksson, J. Rudholm, A. Wojciechowski. “A method for simulation based optimization using radial basis functions”, Optimization and Engineering, 2010, Vol. 11, Issue 4, pp. 501-532.
[15] J. Rudholm, and A. Wojciechowski, “A method for simulation based optimization using radial basis functions”, Master’s theses, Chalmers, 2007.
[16] A. Samad, K. Y. Kim, T. Goel, R. T. Haftka, and W. Shyy, “Multiple surrogate modeling for axial compressor blade shape optimization”, Journal of Propulsion and Power, Vol. 24, No. 2, 2008, pp. 302–310.
[17] F. A. C. Viana, “Multiple surrogates for prediction and optimization”, PhD Dissertation, Department of Mechanical and Aerospace Engineering, University of Florida, Gainesville, FL, USA, May, 2011.
[18] J. Surowiecki, “The Wisdom of Crowds”, New York: Anchor Books, 2004.
[19] S. E. Page, “The Difference: How the Power of Diversity Creates Better Groups, Firms, Schools, and Societies”, Princeton, NJ: Princeton University Press, 2007.
[20] J. Lorenz, H. Rauhut, F. Schweitzer, and D. Helbing, “How social influence can undermine the wisdom of crowd effect”, Proc. Nat. Acad. Sciences, 108 (22), 2011, pp. 9020-9025.
[21] M. J. Sasena, “Flexibility and Efficiency Enhancements for Constrained Global Design Optimization with Kriging Approximations”, Ph.D. Dissertation, Department of Mechanical Engineering, University of Michigan, Ann Arbor, MI, 2002.
[22] J. P. C. Kleijnen, and W. C. M. van Beers, “Application-driven sequential designs for simulation experiments: kriging metamodelling,” The Journal of the Operational Research Society, Vol. 55, No. 8, 2004, pp. 876–883.
[23] S. Lophaven, H. B. Nielsen, and J. Søndergaard, “DACE - A MATLAB Kriging Toolbox”, Technical University of Denmark, 2002.
[24] R. Franke, “Scattered data interpolation: tests of some methods”, Mathematics of Computation, Vol. 38, No. 157, 1982, pp. 181–200.
[25] B. Fornberg, and J. Zuev, “The Runge Phenomenon and Spatially Variable Shape Parameters in RBF Interpolation”, Computers & Mathematics with Applications, Vol. 54, Issue 3, 2007, pp. 379-398.
[26] J. P. Boyd, “Six strategies for defeating the Runge Phenomenon in Gaussian radial basis functions on a finite interval”, Computers & Mathematics with Applications, Vol. 60, Issue 12, 2010, pp. 3108-3122.
[27] A. Törn, and A. Žilinskas, “Global Optimization”, Springer-Verlag, New York, 1989.
[28] F. Schoen, “A wide class of test functions for global optimization”, Journal of Global Optimization, 1993, pp. 133–137.
[29] B. G. M. Husslage, G. Rennen, E. R. van Dam, D. den Hertog, “Spacefilling Latin hypercube designs for computer experiments”, Optimization and Engineering, Volume 12, Issue 4, 2011, pp. 611-630.