Videos

Sample Average Approximation for Stochastic Programs

Presenter
August 8, 2016
Keywords:
  • stochastic program; sample average approximation; solution quality; sequential sampling
MSC:
  • 90C15
Abstract
Simply evaluating the objective function of a stochastic program can be intractable because of a high-dimensional integral, necessitating approximations. Using a sample mean obtained from Monte Carlo simulation yields a sample average approximation (SAA) to the original stochastic program. We discuss expected and desired results from solving an SAA, comparing and contrasting these with basic results derived for simple sample means. We explore how SAA can be used, in an a posteriori manner, to assess the quality of a given solution, whether obtained by SAA or otherwise. We also discuss how to handle sequential sampling issues that arise naturally when attempting algorithmic control over the quality of a solution.