Stopping Rules for Class of Sampling-Based Stochastic Programming Algorithms
Morton, David P.
MetadataShow full item record
Decomposition and 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. These rules are applied to a multistage stochastic linear programming algorithm due to Pereira and Pinto. Stopping rules, Monte Carlo sampling, Stochastic programming
NPS Report NumberNPS-OR-94-003
Showing items related by title, author, creator and subject.
Singham, Dashi I. (ACM, 2014);The sample size decision is crucial to the success of any sampling experiment. More samples imply better confidence and precision in the results, but require higher costs in terms of time, computing power, and money. ...
Kobayashi, Izumi (Monterey, California. Naval Postgraduate School, 2002-09);We propose two methods of constructing ensembles of classifiers. One method directly injects randomness into classification tree algorithms by choosing a split randomly at each node with probabilities proportional to the ...
Leino, Richard E. (Monterey, California. Naval Postgraduate School, 1996-09);Two algorithms are presented which allow for the unambiguous resolution of multiple undersampled frequency components in a signal. Digital signal processing is usually governed by the Nyquist criterion which limits the ...