Monte Carlo sampling techniques for solving stochastic and large scale deterministic optimization problems

Monday, October 18, 2010 - 11:00am - 12:00pm
Keller 3-180
Alexander Shapiro (Georgia Institute of Technology)
The traditional approach to solving stochastic programming problems is based on construction scenarios representing a discretization of the underline (true) stochastic data process. Consequently, computational complexity of the obtained optimization problem is determined by the number of generated scenarios. Unfortunately the number of scenarios needed to approximate the true distribution of the data process grows exponentially both with increase of the number of random parameters and number of stages. A way of dealing with this explosion of the number of scenarios is to use randomization approaches based on Monte Carlo sampling techniques. In this talk we discuss theoretical and computational aspects of Monte Carlo sampling based approaches to solving two and multi-stage stochastic programming problems. Moreover, certain classes of deterministic problems can be formulated in terms of expected values and consequently randomization techniques can be applied to solve such large scale optimization problems. In particular, we discuss two competing approaches: the Sample Average Approximation (SAA) method and Stochastic Approximation (SA) type algorithms.
MSC Code: