Optimization Online


Central Limit Theorem and Sample Complexity of Stationary Stochastic Programs

Alexander Shapiro (ashapiro***at***isye.gatech.edu)
Yi Cheng (cheng.yi***at***gatech.edu)

Abstract: In this paper we discuss sample complexity of solving stationary stochastic programs by the Sample Average Approximation (SAA) method. We investigate this in the framework of Optimal Control (in discrete time) setting. In particular we derive a Central Limit Theorem type asymptotics for the optimal values of the SAA problems. The main conclusion is that the sample size, required to attain a given relative error of the SAA solution, is not sensitive to the discount factor, even if the discount factor is very close to one. We consider the risk neutral and risk averse settings. The presented numerical experiments confirm the theoretical analysis.

Keywords: multistage programs, optimal control, Central Limit Theorem, dynamic programming, Bellman equation, SDDP algorithm, risk averse approach

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 05/18/2021
Entry Accepted: 05/18/2021
Entry Last Modified: 07/08/2021

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 Optimization Society