On Complexity of Multistage Stochastic Programs

Alexander Shapiro (ashapiroisye.gatech.edu)

Abstract: In this paper we derive estimates of the sample sizes required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented analysis is self contained and is based on a, relatively elementary, one dimensional Cramer's Large Deviations Theorem.

Keywords: stochastic programming, Monte Carlo sampling, sample average method, large deviations exponential bounds, complexity.

Category 1: Stochastic Programming

Citation: Working paper, Georgia Institute of Technology, Atlanta, GA

Download: [PDF]

Entry Submitted: 01/06/2005
Entry Accepted: 01/07/2005
Entry Last Modified: 01/24/2005

Modify/Update this entry