Evaluation of a Surrogate Based Method for Global Optimization

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.

Authors:

• David Lindström

Keywords:

• Expensive function
• infill sampling criterion
• kriging
• global optimization
• response surface
• Runge phenomenon.

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.