Branch and bound algorithms for maximizing expected improvement functions
From MaRDI portal
Publication:710752
DOI10.1016/J.JSPI.2010.05.011zbMATH Open1197.62117arXiv1003.0804OpenAlexW2121437933MaRDI QIDQ710752FDOQ710752
Authors: Mark Franey, Pritam Ranjan, Hugh Chipman 
Publication date: 22 October 2010
Published in: Journal of Statistical Planning and Inference (Search for Journal in Brave)
Abstract: Deterministic computer simulations are often used as a replacement for complex physical experiments. Although less expensive than physical experimentation, computer codes can still be time-consuming to run. An effective strategy for exploring the response surface of the deterministic simulator is the use of an approximation to the computer code, such as a Gaussian process (GP) model, coupled with a sequential sampling strategy for choosing design points that can be used to build the GP model. The ultimate goal of such studies is often the estimation of specific features of interest of the simulator output, such as the maximum, minimum, or a level set (contour). Before approximating such features with the GP model, sufficient runs of the computer simulator must be completed. Sequential designs with an expected improvement (EI) function can yield good estimates of the features with a minimal number of runs. The challenge is that the expected improvement function itself is often multimodal and difficult to maximize. We develop branch and bound algorithms for efficiently maximizing the EI function in specific problems, including the simultaneous estimation of a minimum and a maximum, and in the estimation of a contour. These branch and bound algorithms outperform other optimization strategies such as genetic algorithms, and over a number of sequential design steps can lead to dramatically superior accuracy in estimation of features of interest.
Full work available at URL: https://arxiv.org/abs/1003.0804
Recommendations
- Expected improvement in efficient global optimization through bootstrapped Kriging
- Multiobjective optimization of expensive-to-evaluate deterministic computer simulator models
- On the convergence rates of expected improvement methods
- scientific article; zbMATH DE number 1556153
- Efficient global optimization of expensive black-box functions
Sequential statistical design (62L05) Applications of mathematical programming (90C90) Applications of statistics to physics (62P35)
Cites Work
- Efficient global optimization of expensive black-box functions
- Interpolation of spatial data. Some theory for kriging
- The design and analysis of computer experiments.
- Design and analysis of computer experiments. With comments and a rejoinder by the authors
- Title not available (Why is that?)
- A taxonomy of global optimization methods based on response surfaces
- An informational approach to the global optimization of expensive-to-evaluate functions
- Branch-and-Bound Methods: A Survey
- Global optimization to prescribed accuracy
- Branch and bound algorithm for computing the minimum stability degree of parameter‐dependent linear systems
- On the design of optimization strategies based on global response surface approximation models
Cited In (5)
- A Sequential Design Approach for Calibrating Dynamic Computer Simulators
- Computer simulation-based optimisation: hybrid branch and bound and orthogonal array-based enumeration algorithm
- Expected improvement for expensive optimization: a review
- On the choice of the low-dimensional domain for global optimization via random embeddings
- Expected improvement in efficient global optimization through bootstrapped Kriging
Uses Software
This page was built for publication: Branch and bound algorithms for maximizing expected improvement functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q710752)
