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

Alexander Shapiro, Tito Homem-De-Mello

Producción científica: Contribución a una revistaArtículorevisión exhaustiva

184 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Páginas (desde-hasta)70-86
Número de páginas17
PublicaciónSIAM Journal on Optimization
Volumen11
N.º1
DOI
EstadoPublicada - 2000
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs'. En conjunto forman una huella única.

Citar esto