Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse

作     者：Chen, ZL Powell, WB 

作者机构：Univ Penn Dept Syst Engn Philadelphia PA 19104 USA Princeton Univ Dept Civil Engn & Operat Res Princeton NJ 08544 USA 

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

年 卷 期：1999年第102卷第3期

页      面：497-524页

核心收录：

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

基　　金：Air Force Office of Scientific Research  AFOSR 

主　　题：multistage stochastic programming cutting planes sampling convergence with probability one 

摘      要：We propose an algorithm for multistage stochastic linear programs with recourse where random quantities in different stages are independent. The algorithm approximates successively expected recourse functions by building up valid cutting planes to support these functions from below. In each iteration, for the expected recourse function in each stage, one cutting plane is generated using the dual extreme points of the next-stage problem that have been found so far. We prove that the algorithm is convergent with probability one.