Complexity of stochastic dual dynamic programming

DOI10.1007/S10107-020-01567-1zbMATH Open1489.90082OpenAlexW3084898007MaRDI QIDQ2118093FDOQ2118093

Authors Guanghui Lan 

Publication date 22 March 2022

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.07702

Mathematics Subject Classification ID

Convex programming (90C25) Numerical methods based on nonlinear programming (49M37) Semidefinite programming (90C22) Stochastic programming (90C15) Decentralized systems (93A14)

Abstract: Stochastic dual dynamic programming is a cutting plane type algorithm for multi-stage stochastic optimization originated about 30 years ago. In spite of its popularity in practice, there does not exist any analysis on the convergence rates of this method. In this paper, we first establish the number of iterations, i.e., iteration complexity, required by a basic dynamic cutting plane method for solving relatively simple multi-stage optimization problems, by introducing novel mathematical tools including the saturation of search points. We then refine these basic tools and establish the iteration complexity for both deterministic and stochastic dual dynamic programming methods for solving more general multi-stage stochastic optimization problems under the standard stage-wise independence assumption. Our results indicate that the complexity of some deterministic variants of these methods mildly increases with the number of stages $T$, in fact linearly dependent on $T$ for discounted problems. Therefore, they are efficient for strategic decision making which involves a large number of stages, but with a relatively small number of decision variables in each stage. Without explicitly discretizing the state and action spaces, these methods might also be pertinent to the related reinforcement learning and stochastic control areas.

Recommendations

• Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization
• Analysis of stochastic dual dynamic programming method
• On the convergence of stochastic dual dynamic programming and related methods
• Inexact cuts in stochastic dual dynamic programming
• Stochastic dynamic cutting plane for multistage stochastic convex programs

Cites work

• Analysis of stochastic dual dynamic programming method
• Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
• Evaluating policies in risk-averse multi-stage stochastic programming
• Exact converging bounds for stochastic dual dynamic programming via Fenchel duality
• First-order and stochastic optimization methods for machine learning
• Introduction to Stochastic Programming
• Introductory lectures on convex optimization. A basic course.
• Lectures on Stochastic Programming
• MIDAS: a mixed integer dynamic approximation scheme
• Multi-stage stochastic optimization applied to energy planning
• On complexity of multistage stochastic programs
• On complexity of stochastic programming problems
• On solving multistage stochastic programs with coherent risk measures
• On the convergence of decomposition methods for multistage stochastic convex programs
• On the convergence of sampling-based decomposition algorithms for multistage stochastic programs
• Robust Dual Dynamic Programming
• SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning
• Scenarios and Policy Aggregation in Optimization Under Uncertainty
• Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse
• Stochastic dual dynamic integer programming
• The Cutting-Plane Method for Solving Convex Programs
• The abridged nested decomposition method for multistage stochastic linear programs with relatively complete recourse
• Validation analysis of mirror descent stochastic approximation method

Cited in

(15)

• Correction to: ``Complexity of stochastic dual dynamic programming
• Improving the performance of stochastic dual dynamic programming
• scientific article; zbMATH DE number 4095287 (Why is no real title available?)
• Stochastic iterative dynamic programming: a Monte Carlo approach to dual control
• scientific article; zbMATH DE number 7733446 (Why is no real title available?)
• Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization
• Dynamic stochastic approximation for multi-stage stochastic optimization
• Modeling time-dependent randomness in stochastic dual dynamic programming
• Analysis of stochastic dual dynamic programming method
• About the Complexity of Two-Stage Stochastic IPs
• Stochastic convexity in dynamic programming
• Decomposition of convex high dimensional aggregative stochastic control problems
• Stochastic Gauss-Newton algorithm with STORM estimators for nonconvex composite optimization
• scientific article; zbMATH DE number 7733443 (Why is no real title available?)
• Exact Quantization of Multistage Stochastic Linear Problems

This page was built for publication: Complexity of stochastic dual dynamic programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118093)