Single Observation Adaptive Search for Continuous Simulation Optimization

• 成果类型: Article
• 署名作者: Kiatsupaibul, Seksan; Smith, Robert L.; Zabinsky, Zelda B.
• 署名单位: Chulalongkorn University; University of Michigan System; University of Michigan; University of Washington; University of Washington Seattle
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1759
• 发表日期: 2018
• 页码: 1713-1727
• 关键词: interacting-particle algorithm

摘要

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.