Optimal Budget Allocation for Sample Average Approximation

• 成果类型: Article
• 署名作者: Royset, Johannes O.; Szechtman, Roberto
• 署名单位: United States Department of Defense; United States Navy; Naval Postgraduate School
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2013.1163
• 发表日期: 2013
• 页码: 762-776
• 关键词: simulation optimization; stochastic optimization; BEHAVIOR

摘要

The sample average approximation approach to solving stochastic programs induces a sampling error, caused by replacing an expectation by a sample average, as well as an optimization error due to approximating the solution of the resulting sample average problem. We obtain estimators of an optimal solution and the optimal value of the original stochastic program after executing a finite number of iterations of an optimization algorithm applied to the sample average problem. We examine the convergence rate of the estimators as the computing budget tends to infinity, and we characterize the allocation policies that maximize the convergence rate in the case of sublinear, linear, and superlinear convergence regimes for the optimization algorithm.