On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs

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 a...

Full description

Saved in:
Bibliographic Details
Published in:Mathematics of operations research 2015-02, Vol.40 (1), p.130-145
Main Authors: Girardeau, P., Leclere, V., Philpott, A. B.
Format: Article
Language:English
Subjects:
Benders decomposition
Convergence (Mathematics)
Convex analysis
Convex programming
Decomposition (Mathematics)
Dynamic programming
Mathematical research
Mathematics
Monte-Carlo sampling
Optimization algorithms
Optimization and Control
Sampling techniques
stochastic dual dynamic programming algorithm
Stochastic models
Stochastic programming
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0364-765X
1526-5471
DOI:10.1287/moor.2014.0664