On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs

• 成果类型: Article
• 署名作者: Girardeau, P.; Leclere, V.; Philpott, A. B.
• 署名单位: Institut Polytechnique de Paris; Ecole des Ponts ParisTech; University of Auckland
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2014.0664
• 发表日期: 2015
• 页码: 130-145
• 关键词: cutting-plane

摘要

We prove the almost-sure convergence of a class of sampling-based nested decomposition algorithms for multistage stochastic convex programs in which the stage costs are general convex functions of the decisions and uncertainty is modelled by a scenario tree. As special cases, our results imply the almost-sure convergence of stochastic dual dynamic programming, cutting-plane and partial-sampling (CUPPS) algorithm, and dynamic outer-approximation sampling algorithms when applied to problems with general convex cost functions.