Optimization Online


On Complexity of Multistage Stochastic Programs

Alexander Shapiro (ashapiro***at***isye.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society