On the convergence of decomposition methods for multi-stage stochastic convex programs

P. Girardeau (pierre.girardeauensta.org)
V. Leclere (vincent.leclerecermics.enpc.fr)
A. B. Philpott (a.philpottauckland.ac.nz)

Abstract: 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 SDDP, CUPPS and DOASA when applied to problems with general convex cost functions.

Keywords: Stochastic Programming, Dynamic Programming, Stochastic Dual Dynamic Programming algorithm, Monte-Carlo sampling, Benders decomposition

Category 1: Stochastic Programming

Category 2: Other Topics (Dynamic Programming )

Category 3: Convex and Nonsmooth Optimization (Convex Optimization )

Citation:

Download: [PDF]

Entry Submitted: 04/24/2012
Entry Accepted: 04/25/2012
Entry Last Modified: 05/25/2013

Modify/Update this entry