Stopping Rules for a Class of Sampling-Based Stochastic Programming Algorithms
Stopping Rules for a Class of Sampling-Based Stochastic Programming Algorithms
复制标题
一类基于采样的随机规划算法的停止规则
作者：
D. Morton
基于蒙特卡罗采样的算法在解决具有许多场景的随机程序方面具有很大的前景。这种算法的一个关键组成部分是一个停止准则，以确保解决方案的质量。本文针对一类通过抽样估计最优目标函数值界的算法，提出了停止规则理论。我们提供了选择样本大小和终止算法的规则，在这些规则下，可以验证所提出的解决方案质量的置信区间的渐近有效性。给出了一个简单实例的实证覆盖率结果。
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.