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

被引：62

作者：

Chen, ZL ^{[1
]}

Powell, WB

机构：

[1] Univ Penn, Dept Syst Engn, Philadelphia, PA 19104 USA

[2] Princeton Univ, Dept Civil Engn & Operat Res, Princeton, NJ 08544 USA

来源：

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS | 1999年 / 102卷 / 03期

关键词：

multistage stochastic programming; cutting planes; sampling; convergence with probability one;

D O I：

10.1023/A:1022641805263

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：497 / 524

页数：28

共 24 条

[21] On augmented Lagrangian decomposition methods for multistage stochastic programs [J].