Tractable Reformulations of Distributionally Robust Two-stage Stochastic Programs with $\infty -$Wasserstein Distance

Abstract

In the optimization under uncertainty, decision-makers first select a wait-and-see policy before any realization of uncertainty and then place a here-and-now decision after the uncertainty has been observed. Two-stage stochastic programming is a popular modeling paradigm for the optimization under uncertainty that the decision-makers first specifies a probability distribution, and then seek the best decisions to jointly optimize the deterministic wait-and-see and expected here-and-now costs. In practice, such a probability distribution may not be fully available but is probably observable through an empirical dataset. Therefore, this paper studies distributionally robust two-stage stochastic program (DRTSP) which jointly optimizes the deterministic wait-and-see and worst-case expected here-and-now costs, and the probability distribution comes from a family of distributions which are centered at the empirical distribution using $\infty -$Wasserstein metric. There have been successful developments on deriving tractable approximations of the worst-case expected here-and-now cost in DRTSP. Unfortunately, limited results on exact tractable reformulations of DRTSP. This paper fills this gap by providing sufficient conditions under which the worst-case expected here-and-now cost in DRTSP can be efficiently computed via a tractable convex program. By exploring the properties of binary variables, the developed reformulation techniques are extended to DRTSP with binary random parameters. The main tractable reformulations in this paper are projected into the original decision space and thus can be interpreted as conventional two-stage stochastic programs under discrete support with extra penalty terms enforcing the robustness. These tractable results are further demonstrated to be sharp through complexity analysis.

arXiv comment31 pages

References in corpus (4)

• Robust Wasserstein Profile Inference and Applications to Machine Learning
• Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls
• Decomposition Algorithm for Distributionally Robust Optimization using Wasserstein Metric
• Two-stage sample robust optimization

Cited by in corpus (4)

• Distributionally Robust Local Non-parametric Conditional Estimation
• Distributionally Robust Bottleneck Combinatorial Problems: Uncertainty Quantification and Robust Decision Making
• Second-order Conic Programming Approach for Wasserstein Distributionally Robust Two-stage Linear Programs
• Stochastic Decomposition Method for Two-Stage Distributionally Robust Optimization