AM  Vol.5 No.2 , January 2014
Finding and Choosing among Multiple Optima
ABSTRACT

Black box functions, such as computer experiments, often have multiple optima over the input space of the objective function. While traditional optimization routines focus on finding a single best optimum, we sometimes want to consider the relative merits of multiple optima. First we need a search algorithm that can identify multiple local optima. Then we consider that blindly choosing the global optimum may not always be best. In some cases, the global optimum may not be robust to small deviations in the inputs, which could lead to output values far from the optimum. In those cases, it would be better to choose a slightly less extreme optimum that allows for input deviation with small change in the output; such an optimum would be considered more robust. We use a Bayesian decision theoretic approach to develop a utility function for selecting among multiple optima.


Cite this paper
J. Guenther, H. Lee and G. Gray, "Finding and Choosing among Multiple Optima," Applied Mathematics, Vol. 5 No. 2, 2014, pp. 300-317. doi: 10.4236/am.2014.52031.
References
[1]   K. C. Tan, E. F. Khor and T. H. Lee, “Multiobjective Evolutionary Algorithms and Applications,” Springer, Berlin, 2005.

[2]   E. Zitler and L. Thiele, “Multiobjective Evolutionary Algorithms: A Comparative Case Study,” IEEE Transactions on Evolutionary Computation, Vol. 3, No. 4, 1999, pp. 257-271.
http://dx.doi.org/10.1109/4235.797969

[3]   D. E. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison Wesley, 1989.

[4]   J. H. Holland, “Adaption in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, 1975.

[5]   J. H. Holland, “Genetic Algorithms and the Optimal Allocation of Trials,” SIAM Journal on Computing, Vol. 2, No. 2, 1975, pp. 88-105.

[6]   J. Kennedy and R. C. Eberhart, “Particle Swarm Optimization,” IEEE International Conference on Neural Networks, Piscataway, 1995.

[7]   T. Santner, B. Williams and W. Notz, “The Design and Analysis of Computer Experiments,” Springer, Berlin, 2003.
http://dx.doi.org/10.1007/978-1-4757-3799-8

[8]   R. Gramacy and H. Lee, “Bayesian Treed Gaussian Process Models with Application to Computer Modeling,” Journal of the American Statistical Association, Vol. 103, No. 483, 2008, pp. 1119-1130. http://dx.doi.org/10.1198/016214508000000689

[9]   A. Gelman, J. B. Carlin, H. S. Stern and D. B. Rubin, “Bayesian Data Analysis,” Chapman & Hall, London, 2004.

[10]   M. Taddy, H. Lee, G. Gray and J. Griffin, “Bayesian Guided Pattern Search for Robust Local Optimization,” Technometrics, Vol. 51, No. 4, 2009, pp. 389-401.
http://dx.doi.org/10.1198/TECH.2009.08007

[11]   L. Bastos and A. O’Hagan, “Diagnostics for Gaussian Process Emulators,” Technometrics, Vol. 51, No. 4, 2009, pp. 425-438.
http://dx.doi.org/10.1198/TECH.2009.08019

[12]   H. Lee, R. Gramacy, C. Linkletter and G. Gray, “Optimization Subject to Hidden Constraints via Statistical Emulation,” Pacific Journal of Optimization, Vol. 7, No. 3, 2011, pp. 467-478.

[13]   D. Jones, M. Shonlau and W. Welch, “Efficient Global Optimization of Expensive Blackbox Functions,” Journal of Global Optimization, Vol. 13, No. 4, 1998, pp. 455-492.
http://dx.doi.org/10.1023/A:1008306431147

[14]   G. A. Gray and T. G. Kolda, “Algorithm 856: APPSPACK 4.0: Asynchronous Parallel Pattern Search for Derivative-Free Optimization,” ACM Transactions on Mathematical Software, Vol. 32, No. 3, 2006, pp. 485-507.

[15]   S. M. Wild and C. A. Shoemaker, “Global Convergence of Radial Basis Function Trust Region Algorithms for Derivative-Free Optimization,” SIAM Review, Vol. 55, No. 2, 2013, pp. 349-371. http://dx.doi.org/10.1137/120902434

[16]   J. Berger, “Statistical Decision Theory and Bayesian Analysis,” Springer-Verlag, Berlin, 1985.
http://dx.doi.org/10.1007/978-1-4757-4286-2

[17]   M. H. DeGroot, “Optimal Statistical Decisions,” Wiley, New York, 2004.
http://dx.doi.org/10.1002/0471729000

[18]   R. B. Gramacy, “Tgp: An R Package for Bayesian Nonstationary, Semiparametric Nonlinear Regression and Design by Treed Gaussian Process Models,” Journal of Statistical Software, Vol. 19, No. 9, 2007, pp. 1-48.

[19]   A.-R. Hedar and M. Fukushima, “Tabu Search Directed by Direct Search Methods for Nonlinear Global Optimization,” European Journal of Operational Research, Vol. 127, No. 2, 2006, pp. 329-349. http://dx.doi.org/10.1016/j.ejor.2004.05.033

[20]   L. S. Matott, K. Leung and J. Sim, “Application of Matlab and Python Optimizers to Two Case-Studies Involving Groundwater and Contaminant Transport Modeling,” Geospatial Cyberinfrastructure for Polar Research, Vol. 37, No. 11, 2011, pp. 18941899.

 
 
Top