Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

Abstract

Adaptive robust optimization problems are usually solved approximately by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximation error can be substantial. In this paper we show that two-stage robust and distributionally robust linear programs can often be reformulated exactly as conic programs that scale polynomially with the problem dimensions. Specifically, when the ambiguity set constitutes a 2-Wasserstein ball centered at a discrete distribution, then the distributionally robust linear program is equivalent to a copositive program (if the problem has complete recourse) or can be approximated arbitrarily closely by a sequence of copositive programs (if the problem has sufficiently expensive recourse). These results directly extend to the classical robust setting and motivate strong tractable approximations of two-stage problems based on semidefinite approximations of the copositive cone. We also demonstrate that the two-stage distributionally robust optimization problem is equivalent to a tractable linear program when the ambiguity set constitutes a 1-Wasserstein ball centered at a discrete distribution and there are no support constraints.

References in corpus (3)

• A Model of Inductive Bias Learning
• Distributionally Robust Stochastic Optimization with Wasserstein Distance
• Sample Out-Of-Sample Inference Based on Wasserstein Distance

Cited by in corpus (26)

• Optimization under Uncertainty in the Era of Big Data and Deep Learning: When Machine Learning Meets Mathematical Programming
• Distributionally Robust Optimization: A Review
• Sample Robust Scheduling of Electricity-Gas Systems Under Wind Power Uncertainty
• Optimal Transport Based Distributionally Robust Optimization: Structural Properties and Iterative Schemes
• On Distributionally Robust Chance Constrained Programs with Wasserstein Distance
• Tutorials on Advanced Optimization Methods
• Data-Driven Distributionally Robust Appointment Scheduling over Wasserstein Balls
• Two-stage sample robust optimization
• Incorporating statistical model error into the calculation of acceptability prices of contingent claims
• Data-Driven Distributionally Robust Optimization for Long-Term Contract vs. Spot Allocation Decisions: Application to Electricity Markets
• Practicable Robust Stochastic Optimization under Divergence Measures
• Conic Reformulations for Kullback-Leibler Divergence Constrained Distributionally Robust Optimization and Applications
• Tractable Reformulations of Distributionally Robust Two-stage Stochastic Programs with $\infty -$Wasserstein Distance
• Copositive Duality for Discrete Markets and Games
• A Copositive Approach for Two-Stage Adjustable Robust Optimization with Uncertain Right-Hand Sides
• Distributionally Robust Bottleneck Combinatorial Problems: Uncertainty Quantification and Robust Decision Making
• The discrete moment problem with nonconvex shape constraints
• Frank-Wolfe Methods in Probability Space
• A semi-proximal augmented Lagrangian based decomposition method for primal block angular convex composite quadratic conic programming problems
• Robust Stochastic Optimization with Rare-Event Modeling
• Second-order Conic Programming Approach for Wasserstein Distributionally Robust Two-stage Linear Programs
• A Data-Driven Distributionally Robust Bound on the Expected Optimal Value of Uncertain Mixed 0-1 Linear Programming
• Approximation Algorithms for Distributionally Robust Stochastic Optimization with Black-Box Distributions
• Stochastic Decomposition Method for Two-Stage Distributionally Robust Optimization
• Extended Trust-Region Problems with One or Two Balls: Exact Copositive and Lagrangian Relaxations
• Data-driven two-stage conic optimization with zero-one uncertainties