On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs

Alexander Shapiro, Tito Homem-De-Mello

Research output: Contribution to journalArticlepeer-review

174 Scopus citations

Abstract

In this paper we discuss Monte Carlo simulation based approximations of a stochastic programming problem. We show that if the corresponding random functions are convex piecewise linear and the distribution is discrete, then an optimal solution of the approximating problem provides an exact optimal solution of the true problem with probability one for sufficiently large sample size. Moreover, by using the theory of large deviations, we show that the probability of such an event approaches one exponentially fast with increase of the sample size. In particular, this happens in the case of linear two- (or multi-) stage stochastic programming with recourse if the corresponding distributions are discrete. The obtained results suggest that, in such cases, Monte Carlo simulation based methods could be very efficient. We present some numerical examples to illustrate the ideas involved.

Original languageEnglish
Pages (from-to)70-86
Number of pages17
JournalSIAM Journal on Optimization
Volume11
Issue number1
DOIs
StatePublished - 2000
Externally publishedYes

Keywords

  • Convex analysis
  • Large deviations theory
  • Monte Carlo simulation
  • Two-stage stochastic programming with recourse

Fingerprint

Dive into the research topics of 'On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs'. Together they form a unique fingerprint.

Cite this