On Rate of Convergence of Optimal Solutions of Monte Carlo Approximations of Stochastic Programs
Shapiro, Alexander
Homem-de-Mello, Tito
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik
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 smooth and the distribution is discrete, then (under mild additional assumptions) an opitmal 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 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 two 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 involved ideas.