Stochastic decomposition method for two-stage distributionally robust linear optimization

DOI10.1137/20M1378600zbMATH Open1497.90140arXiv2011.08376MaRDI QIDQ5097017FDOQ5097017

Manish Kumar Bansal, Harsha Gangammanavar

Publication date: 19 August 2022

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

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).

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

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

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)

Cites Work

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

Cited In (5)

• A model of distributionally robust two-stage stochastic convex programming with linear recourse
• 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
• Distributionally Robust Two-Stage Stochastic Programming

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)