On Distributionally Robust Multistage Convex Optimization: New Algorithms and Complexity Analysis

2020/10/14 by Shixuan Zhang, Xu Andy Sun, Zhang, Shixuan +1
Computer Science · Decision Sciences · Engineering · #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Mathematical Programming #Optimization and Variational Analysis #Risk and Portfolio Optimization

paper · pdf · doi:10.48550/arxiv.2010.06759

openalex publication_date 2020/10/14 · openalex created_date 2020/10/22 · openalex updated_date 2026/07/28

Abstract

This paper presents an algorithmic study and complexity analysis for solving distributionally robust multistage convex optimization (DR-MCO) problems. Our main contribution is a novel nonconsecutive dual dynamic programming (NDDP) algorithm which explores different stages in an adaptive fashion. In contrast with the usual consecutive dual dynamic programming (CDDP) algorithm, we show that NDDP reduces the subproblem complexity from quadratic to linear dependency on the number of stages. Two different DR-MCO examples are also presented to show the efficiency and effectiveness of the proposed NDDP algorithm.

Citations

• A Study of Distributionally Robust Multistage Stochastic Optimization
• Stochastic dual dynamic integer programming
• Complexity of Stochastic Dual Dynamic Programming

Related

• On Distributionally Robust Multistage Convex Optimization: Data-driven Models and Performance
• Efficient Algorithms for Distributionally Robust Stochastic Optimization with Discrete Scenario Support
• A Cutting-plane and Benders' Decomposition Algorithm for Two-Stage Distributionally Robust Convex programs
• Distributionally Robust Optimization with Polynomial Robust Constraints
• On Tractability, Complexity, and Mixed-Integer Convex Programming Representability of Distributionally Favorable Optimization