Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization

DOI10.1007/S10107-022-01875-8MaRDI QIDQ2097671zbMATH OpenOpenAlexWikidataFDO

Authors Shixuan Zhang, Xu Andy Sun

Publication date 14 November 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

complexity analysisMINLPmultistage stochastic programmingSDDP

Mathematics Subject Classification ID

Nonlinear programming (90C30) Dynamic programming (90C39) Stochastic programming (90C15) Abstract computational complexity for mathematical programming problems (90C60) Mixed integer programming (90C11) Duality theory (optimization) (49N15)

Abstract: In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization with non-Lipschitzian value functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a $(T+1)$-stage stochastic MINLP with $d$-dimensional state spaces, to obtain an $epsilon$-optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by $mathcalO((frac2Tepsilon{)}^d)$, and is lower bounded by $mathcalO((fracT4epsilon{)}^d)$ for the general case or by $mathcalO((fracT8epsilon{)}^{d/2-1})$ for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity depends polynomially on the number of stages. We further show that the iteration complexity depends linearly on $T$, if all the state spaces are finite sets, or if we seek a $(Tepsilon)$-optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale with $T$. To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs.

Recommendations

• Complexity of stochastic dual dynamic programming
• Stochastic dual dynamic integer programming
• Stochastic dynamic cutting plane for multistage stochastic convex programs
• Stochastic Lipschitz dynamic programming
• Analysis of stochastic dual dynamic programming method

Cites work

• L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
• A Solution Method for Multistage Stochastic Programs with Recourse with Application to an Energy Investment Problem
• A multi-stage stochastic integer programming approach for capacity expansion under uncertainty
• A scenario-based stochastic programming approach for technology and capacity planning
• Analysis of stochastic dual dynamic programming method
• Convergence analysis of sampling-based decomposition methods for risk-averse multistage stochastic convex programs
• Convergent cutting-plane and partial-sampling algorithm for multistage stochastic linear programs with recourse
• Decomposition Principle for Linear Programs
• Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs
• Deterministic electric power infrastructure planning: mixed-integer programming model and nested decomposition algorithm
• Dual dynamic programming with cut selection: convergence proof and numerical experiments
• Exact augmented Lagrangian duality for mixed integer linear programming
• Lectures on convex optimization
• MIDAS: a mixed integer dynamic approximation scheme
• Multi-stage stochastic optimization applied to energy planning
• Nested Decomposition and Multi-Stage Linear Programs
• Nested decomposition for dynamic models
• On the convergence of decomposition methods for multistage stochastic convex programs
• On the convergence of sampling-based decomposition algorithms for multistage stochastic programs
• On the convergence of stochastic dual dynamic programming and related methods
• Partially Adaptive Stochastic Optimization for Electric Power Generation Expansion Planning
• Partitioning procedures for solving mixed-variables programming problems
• Production planning via scenario modelling
• Risk neutral and risk averse stochastic dual dynamic programming method
• Stochastic Lipschitz dynamic programming
• Stochastic Network Programming for Financial Planning Problems
• Stochastic dual dynamic integer programming
• Variational Analysis

Cited in

(15)

• Non-convex nested Benders decomposition
• Special issue: Global solution of integer, stochastic and nonconvex optimization problems
• Stochastic dynamic cutting plane for multistage stochastic convex programs
• Combining sampling-based and scenario-based nested Benders decomposition methods: application to stochastic dual dynamic programming
• A Multistage Stochastic Programming Approach to the Dynamic and Stochastic VRPTW
• Stochastic Lipschitz dynamic programming
• Stochastic Dynamic Linear Programming: A Sequential Sampling Algorithm for Multistage Stochastic Linear Programming
• Complexity of stochastic dual dynamic programming
• Stochastic dual dynamic integer programming
• Optimized ensemble value function approximation for dynamic programming
• Exact Quantization of Multistage Stochastic Linear Problems
• Decomposition methods for global solution of mixed-integer linear programs
• Dual SDDP for risk-averse multistage stochastic programs
• Decomposition of convex high dimensional aggregative stochastic control problems
• scientific article; zbMATH DE number 7733446 (Why is no real title available?)

This page was built for publication: Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization

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