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

DOI10.1007/S10107-022-01875-8zbMATH Open1506.90185arXiv1912.13278OpenAlexW2996830458WikidataQ114228409 ScholiaQ114228409MaRDI QIDQ2097671FDOQ2097671

Authors: Shixuan Zhang, Xu Andy Sun 

Publication date: 14 November 2022

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

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.

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

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

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)

Cites Work

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

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 Dynamic Linear Programming: A Sequential Sampling Algorithm for Multistage Stochastic Linear Programming
• Stochastic Lipschitz dynamic 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
• Title not available (Why is that?)
• Decomposition of convex high dimensional aggregative stochastic control problems

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)