Convergence properties of two-stage stochastic programming

作     者：Dai, L Chen, CH Birge, JR 

作者机构：Univ Penn Dept Syst Engn Philadelphia PA 19104 USA Northwestern Univ McCormick Sch Engn & Appl Sci Evanston IL USA 

出 版 物：《JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS》 (优选法理论与应用杂志)

年 卷 期：2000年第106卷第3期

页      面：489-509页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：EPRI/ARO, (WO8333-03) University of Pennsylvania Research Foundation National Science Foundation, NSF, (DMI-9523275, DMI-9732173, ECS-9624279) National Science Foundation, NSF Sandia National Laboratories, (BD-0618) Sandia National Laboratories 

主　　题：stochastic programming stochastic optimization sample paths convergence rates empirical means 

摘      要：This paper considers a procedure of two-stage stochastic programming in which the performance function to be optimized is replaced by its empirical mean. This procedure converts a stochastic optimization problem into a deterministic one for which many methods are available. Another strength of the method is that there is essentially no requirement on the distribution of the random variables involved. Exponential convergence for the probability of deviation of the empirical optimum from the true optimum is established using large deviation techniques. Explicit bounds on the convergence rates are obtained for the case of quadratic performance functions. Finally, numerical results are presented for the famous news vendor problem, which lends experimental evidence supporting exponential convergence.