Single Observation Adaptive Search for Continuous Simulation Optimization
Seksan Kiatsupaibul, Robert L. Smith, Zelda B. Zabinsky
Operations Research · 2018 · Volume 66 · Issue 6
Abstract
Optimizing the performance of complex systems modeled by stochastic computer simulations is a challenging task, partly because of the lack of structural properties (e.g., convexity). This challenge is magnified by the presence of random error whereby an adaptive algorithm searching for better designs can at times mistakenly accept an inferior design. In contrast to performing multiple simulations at a design point to estimate the performance of the design, we propose a framework for adaptive search algorithms that executes a single simulation for each design point encountered. Here the estimation errors are reduced by averaging the performances from previously evaluated designs drawn from a shrinking ball around the current design point. We show under mild regularity conditions for continuous design spaces that the accumulated errors, although dependent, form a martingale process, and hence, by the strong law of large numbers for martingales, the average errors converge to zero as the algorithm proceeds. This class of algorithms is shown to converge to a global optimum with probability one. By employing a shrinking ball approach with single observations, an adaptive search algorithm can simultaneously improve the estimates of performance while exploring new and potentially better design points. Numerical experiments offer empirical support for this paradigm of single observation simulation optimization. The e-companion is available at https://doi.org/10.1287/opre.2018.1759 .
Keywords
simulation optimization, adaptive search, martingale processes
Enable JavaScript for citation tools and additional paper interactions.