Finding and Choosing among Multiple Optima
- 1 Department of Applied Mathematics and Statistics, University of California, Santa Cruz, USA
- 2 Department of Applied Mathematics and Statistics, University of California, Santa Cruz, USA
- 3 Quantitative Modeling and Analysis, Sandia National Laboratories, Livermore, USA
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 mul tiple 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.
- K. C. Tan, E. F. Khor and T. H. Lee, “Multiobjective Evolutionary Algorithms and Applications,” Springer, Berlin, 2005.
- 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
- D. E. Goldberg, “Genetic Algorithms in Search, Optimization, and Machine Learning,” Addison Wesley, 1989.
- J. H. Holland, “Adaption in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, 1975.
- J. H. Holland, “Genetic Algorithms and the Optimal Allocation of Trials,” SIAM Journal on Computing, Vol. 2, No. 2, 1975, pp. 88-105.
- J. Kennedy and R. C. Eberhart, “Particle Swarm Optimization,” IEEE International Conference on Neural Networks, Piscataway, 1995.
- 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
- 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
- A. Gelman, J. B. Carlin, H. S. Stern and D. B. Rubin, “Bayesian Data Analysis,” Chapman & Hall, London, 2004.
- 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
- 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
- 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.
- 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
- 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.