Complexity of stochastic dual dynamic programming

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

Guanghui Lan

Publication date: 22 March 2022

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Introductory lectures on convex optimization. A basic course.
• Multi-stage stochastic optimization applied to energy planning
• On the convergence of sampling-based decomposition algorithms for multistage stochastic programs
• The Cutting-Plane Method for Solving Convex Programs
• Lectures on Stochastic Programming
• Introduction to Stochastic Programming
• Analysis of stochastic dual dynamic programming method
• Scenarios and Policy Aggregation in Optimization Under Uncertainty
• Validation analysis of mirror descent stochastic approximation method
• On complexity of multistage stochastic programs
• Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse
• On Solving Multistage Stochastic Programs with Coherent Risk Measures
• SDDP for some interstage dependent risk-averse problems and application to hydro-thermal planning
• Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
• On the Convergence of Decomposition Methods for Multistage Stochastic Convex Programs
• Evaluating policies in risk-averse multi-stage stochastic programming
• Stochastic dual dynamic integer programming
• Robust Dual Dynamic Programming
• First-order and stochastic optimization methods for machine learning
• MIDAS: a mixed integer dynamic approximation scheme
• Exact Converging Bounds for Stochastic Dual Dynamic Programming via Fenchel Duality

Cited In (8)

• Stochastic Gauss-Newton algorithm with STORM estimators for nonconvex composite optimization
• Correction to: ``Complexity of stochastic dual dynamic programming
• Modeling time-dependent randomness in stochastic dual dynamic programming
• Title not available (Why is that?)
• Exact Quantization of Multistage Stochastic Linear Problems
• About the Complexity of Two-Stage Stochastic IPs
• Stochastic convexity in dynamic programming
• Decomposition of convex high dimensional aggregative stochastic control 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)