Importance sampling in stochastic programming: A Markov Chain Monte Carlo approach

摘要

Stochastic programming models require optimization algorithms to evaluate expected future costs of current decisions, known as recourse functions. Due to prevailing difficulty, the recourse function has to be estimated using simulation techniques that may require numerous functional evaluations to produce accurate results. An importance sampling framework is proposed for stochastic programming that can produce accurate estimates of the recourse function using a small number of samples. This framework combines Markov Chain Monte Carlo methods with kernel density estimation algorithms which can produce a lower-variance estimate of the recourse function. Warious well- known multistage stochastic programming problems are also used to demonstrate increased accuracy and efficiency of the proposed approach. Based on numerical results it is shown that the proposed importance sampling framework can produce more accurate estimates of the optimal value of stochastic programming models.