Stochastic decomposition method for two-stage distributionally robust linear optimization

DOI10.1137/20M1378600MaRDI QIDQ5097017zbMATH OpenFDO

Authors Harsha Gangammanavar, Manish Kumar Bansal

Publication date 19 August 2022

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

stochastic programmingcutting plane methodsequential samplingdistributionally robust optimizationstochastic decomposition

Mathematics Subject Classification ID

Large-scale problems in mathematical programming (90C06) Stochastic programming (90C15) Minimax problems in mathematical programming (90C47) Robustness in mathematical programming (90C17)

Abstract: In this paper, we present a sequential sampling-based algorithm for the two-stage distributionally robust linear programming (2-DRLP) models. The 2-DRLP models are defined over a general class of ambiguity sets with discrete or continuous probability distributions. The algorithm is a distributionally robust version of the well-known stochastic decomposition algorithm of Higle and Sen (Math. of OR 16(3), 650-669, 1991) for a two-stage stochastic linear program. We refer to the algorithm as the distributionally robust stochastic decomposition (DRSD) method. The key features of the algorithm include (1) it works with data-driven approximations of ambiguity sets that are constructed using samples of increasing size and (2) efficient construction of approximations of the worst-case expectation function that solves only two second-stage subproblems in every iteration. We identify conditions under which the ambiguity set approximations converge to the true ambiguity sets and show that the DRSD method asymptotically identifies an optimal solution, with probability one. We also computationally evaluate the performance of the DRSD method for solving distributionally robust versions of instances considered in stochastic programming literature. The numerical results corroborate the analytical behavior of the DRSD method and illustrate the computational advantage over an external sampling-based decomposition approach (distributionally robust L-shaped method).

Recommendations

• Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems
• Decomposition Algorithms for Two-Stage Distributionally Robust Mixed Binary Programs
• A decomposition method for distributionally-robust two-stage stochastic mixed-integer conic programs
• A stochastic dual dynamic programming method for two-stage distributionally robust optimization problems
• Distributionally Robust Two-Stage Stochastic Programming

Cites work

• scientific article; zbMATH DE number 3539473 (Why is no real title available?)
• L-Shaped Linear Programs with Applications to Optimal Control and Stochastic Programming
• A New Scenario Decomposition Method for Large-Scale Stochastic Optimization
• A model of distributionally robust two-stage stochastic convex programming with linear recourse
• A sequential sampling procedure for stochastic programming
• Algorithms for the solution of stochastic dynamic minimax problems
• Ambiguous chance constrained problems and robust optimization
• Applying the minimax criterion in stochastic recourse programs
• Assessing solution quality in stochastic programs
• Conic programming reformulations of two-stage distributionally robust linear programs over Wasserstein balls
• Convergence analysis for distributionally robust optimization and equilibrium problems
• Data-driven distributionally robust optimization using the Wasserstein metric: performance guarantees and tractable reformulations
• Data-driven risk-averse stochastic optimization with Wasserstein metric
• Decomposition Algorithms for Two-Stage Distributionally Robust Mixed Binary Programs
• Decomposition Principle for Linear Programs
• Decomposition methods for Wasserstein-based data-driven distributionally robust problems
• Distributionally Robust Two-Stage Stochastic Programming
• Distributionally robust optimization under moment uncertainty with application to data-driven problems
• Finite master programs in regularized stochastic decomposition
• Introduction to stochastic programming.
• Lectures on stochastic programming. Modeling and theory.
• Linear programming under uncertainty
• Minimax analysis of stochastic problems
• Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction
• Models and algorithms for distributionally robust least squares problems
• Models for minimax stochastic linear optimization problems with risk aversion
• On a Class of Minimax Stochastic Programs
• On solving two-stage distributionally robust disjunctive programs with a general ambiguity set
• On the rate of convergence in Wasserstein distance of the empirical measure
• Optimal Inequalities in Probability Theory: A Convex Optimization Approach
• Optimal budget allocation for sample average approximation
• Risk-averse two-stage stochastic program with distributional ambiguity
• Scenario-based cuts for structured two-stage stochastic and distributionally robust \(p\)-order conic mixed integer programs
• Scenarios and Policy Aggregation in Optimization Under Uncertainty
• Statistical approximations for stochastic linear programming problems
• Stochastic Decomposition for Two-Stage Stochastic Linear Programs with Random Cost Coefficients
• Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse
• Stochastic Dynamic Linear Programming: A Sequential Sampling Algorithm for Multistage Stochastic Linear Programming
• Stochastic decomposition. A statistical method for large scale stochastic linear programming
• The minimax approach to stochastic programming and an illustrative application

Cited in

(10)

• Distributionally Robust Two-Stage Stochastic Programming
• A decomposition method for distributionally-robust two-stage stochastic mixed-integer conic programs
• A model of distributionally robust two-stage stochastic convex programming with linear recourse
• Decomposition and discrete approximation methods for solving two-stage distributionally robust optimization problems
• A time-consistent Benders decomposition method for multistage distributionally robust stochastic optimization with a scenario tree structure
• A stochastic dual dynamic programming method for two-stage distributionally robust optimization problems
• On solving two-stage distributionally robust disjunctive programs with a general ambiguity set
• Robust two-stage stochastic linear programs with moment constraints
• Decomposition Algorithms for Two-Stage Distributionally Robust Mixed Binary Programs
• A so-called cluster Benders decomposition approach for solving two-stage stochastic linear problems

This page was built for publication: Stochastic decomposition method for two-stage distributionally robust linear optimization

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