-

 

 

 




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

Citation:

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

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society