Stopping rules for a class of sampling-based stochastic programming algorithms
成果类型：
Article
署名作者：
Morton, DP
署名单位：
University of Texas System; University of Texas Austin
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.46.5.710
发表日期：
1998
页码：
710-718
关键词：
摘要：
Monte Carlo sampling-based algorithms hold much promise for solving stochastic programs with many scenarios. A critical component of such algorithms is a stopping criterion to ensure the quality of the solution. In this paper, we develop a stopping rule theory for a class of algorithms that estimate bounds on the optimal objective function value by sampling. We provide rules for selecting sample sizes and terminating the algorithm under which asymptotic validity of confidence intervals for the quality of the proposed solution can be verified. Empirical coverage results are given for a simple example.