TY - JOUR

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

AU - Shapiro, Alexander

AU - Homem-De-Mello, Tito

PY - 2000

Y1 - 2000

N2 - 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.

AB - 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.

KW - Convex analysis

KW - Large deviations theory

KW - Monte Carlo simulation

KW - Two-stage stochastic programming with recourse

UR - http://www.scopus.com/inward/record.url?scp=0034550507&partnerID=8YFLogxK

U2 - 10.1137/S1052623498349541

DO - 10.1137/S1052623498349541

M3 - Article

AN - SCOPUS:0034550507

SN - 1052-6234

VL - 11

SP - 70

EP - 86

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

IS - 1

ER -