Source-linked AI summary
Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls
Grani A. Hanasusanto, Daniel Kuhn
TL;DR
The paper addresses infinite-dimensional two-stage optimization problems that generally can only be solved approximately. It reformulates the original problem as a finite-dimensional conic program of polynomial size and reports that even the coarsest approximations outperform state-of-the-art decision-rule approximations, while extending results to classical robust optimization.
Problem
Two-stage optimization problems involve a continuum of wait-and-see decisions and therefore are typically infinite-dimensional, so they can generally only be solved approximately.
Method
The paper first reformulates the original infinite-dimensional optimization problem as an equivalent finite-dimensional conic program of polynomial size.
Results
Numerical tests suggest that even the coarsest approximations distinctly outperform state-of-the-art decision-rule approximations.
Takeaways & Limitations
The results carry directly over to classical two-stage robust optimization.
Takeaways & Limitations
Replacing the original problem with a finite subset relaxes it and can encourage optimistic bias; a duality gap can also arise in the copositive reformulation.
Abstract
from arXiv · showhide
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.
1 Introduction
Two-stage stochastic, robust, and distributionally robust problems are typically infinite-dimensional and require approximation, often producing optimistic or pessimistic bias. This paper develops polynomial-size conic reformulations and tractable approximations for broad Wasserstein-based two-stage models.
- Problem: Two-stage uncertainty problems involve infinitely many wait-and-see decisions, making them infinite-dimensional and generally solvable only approximately.Existing approximations include support discretization and finite-dimensional decision rules.
- Existing approximations: Support discretization relaxes the original problem and encourages optimistic solutions, whereas decision-rule restrictions produce pessimistic solutions.The two approximation families differ in whether they enlarge or restrict the feasible decision space.
- Method: The paper reformulates the infinite-dimensional problem as an equivalent polynomial-size finite-dimensional conic program, then approximates its cones tractably.This transfers complexity into the cones and enables conservative approximations.
- Conic reformulations: For 2-Wasserstein balls centered at discrete distributions, complete-recourse models admit equivalent polynomial-size copositive programs.This result covers two-stage distributionally robust linear programs with objective and constraint uncertainty.
- Conic reformulations: With sufficiently expensive recourse, the same 2-Wasserstein models can be approximated arbitrarily closely by fixed-polynomial-size copositive programs.Nested tractable inner approximations of the copositive cone yield conservative approximations that can be made arbitrarily accurate.
- Results and scope: Numerical tests suggest even the coarsest tractable approximations outperform state-of-the-art decision-rule approximations, while 1-Wasserstein models without support constraints admit tractable linear programs.The reformulation results also carry over directly to classical two-stage robust optimization with bounded polyhedral uncertainty sets.
2 Problem Formulation
The paper formulates two-stage distributionally robust linear programs using recourse costs under Wasserstein ambiguity around an empirical distribution. It distinguishes sufficiently expensive recourse from complete recourse and connects Wasserstein reformulations to classical robust optimization.
- Model structure: The model separates here-and-now decisions x from the optimal wait-and-see recourse cost Z(x, ξ).The here-and-now objective includes c⊤x, while the recourse problem depends on the uncertain vector ξ.
- Recourse assumptions: Complete recourse requires some y+ with W y+ > 0 and guarantees recourse feasibility for every x and ξ.This stronger condition is imposed only when stronger reformulation results are sought, because it rules out induced constraints.
- Recourse assumptions: Sufficiently expensive recourse requires dual recourse feasibility for every fixed ξ, ensuring Z(x, ξ) > −∞.The paper assumes this condition throughout because it is weak and accommodates many problems with induced constraints.
- Wasserstein ambiguity: The ambiguity set contains distributions close to the empirical distribution formed from I observed samples under a Wasserstein metric.The true distribution is unknown, and the empirical distribution is uniform over the samples ˆξ1, …, ˆξI.
- Reformulation framework: Wasserstein worst-case expectations admit generalized moment and strong dual robust optimization formulations.The reformulation theorem applies to Wasserstein balls centered at empirical distributions and is established using the Knothe–Rosenblatt rearrangement.
- Classical robust limit: When the Wasserstein radius exceeds the uncertainty-set diameter, the model reduces to two-stage robust optimization, independently of sample locations.The worst-case expected cost becomes maxξ∈Ξ Z(x, ξ).
3 Copositive Programming Reformulation
Under a 2-Wasserstein ambiguity set with polyhedral support and sufficiently expensive recourse, the two-stage distributionally robust linear program admits copositive reformulations and convergent approximations.
- Assumptions: A 2-Wasserstein ambiguity set uses the reference distance d(ξ1, ξ2) = ∥ξ1 −ξ2∥2.
- Assumptions: The support set Ξ is assumed to be a non-empty, possibly unbounded polyhedron contained in the non-negative orthant.
- Copositive reformulation: With sufficiently expensive recourse, the distributionally robust linear program admits an equivalent copositive-program reformulation.
- Copositive upper bound: For fixed first-stage decisions, strong linear programming duality and quadratic reformulation yield a finite copositive minimization problem that upper-bounds worst-case expectation.
- Exactness: The copositive and completely positive formulations have matching optimal values, establishing an exact reformulation under complete recourse.
- Approximation: When complete recourse fails, a parameterized copositive family provides bounds and converges to the original optimal value as δ ↓0 when X is compact.
4 Linear Programming Reformulation for Q = 0
Under sufficiently expensive recourse, the two-stage distributionally robust linear program admits an equivalent tractable linear-programming reformulation when uncertainty affects only recourse constraints and the ambiguity set uses a 1-Wasserstein metric. The reformulation also yields distributionally robust LAD and multi-task learning models with norm-dependent regularization.
- Linear reformulation: With Q = 0, Ξ = R^K, a 1-Wasserstein ambiguity set, and sufficiently expensive recourse, problem (1) has an equivalent tractable linear reformulation.The reference distance may use positive scaling parameters w+ and w−; w+ = w− = 1 gives the 1-norm.
- Linear reformulation: The reformulation is derived by dualizing the Wasserstein worst-case expectation and analytically evaluating the resulting maximization and minimization steps.Norm duality, minimax interchange, and linear-programming duality reduce the semi-infinite formulation to finitely many constraints.
- Regression: Distributionally robust LAD regression becomes a tractable model whose empirical LAD loss is supplemented by a norm-dependent regularizer for the regression coefficient.The formulation holds for arbitrary norms; the infinity-norm reference distance recovers the LASSO regularizer, while the 1-norm yields an infinity-norm regularizer.
- Multi-Task Learning: Distributionally robust multi-task learning is likewise an instance of problem (1) and is equivalent to a tractable linear program with regularization for the coefficient matrix and empirical LAD loss.The model simultaneously solves several regression problems and retains the same loss–regularizer decomposition.
- Complexity: For reference distances defined by p-norms with p > 1, computing the optimal value is NP-hard even without first-stage decisions or support constraints.The hardness result follows through a reduction from Matrix Norm Maximization and applies under Q = 0 and r = 1.
5 Numerical Results
The numerical study evaluates copositive-cone and quadratic decision-rule approximations, then compares Wasserstein, Chebyshev, and SAA policies out of sample. The copositive approximation is substantially tighter, while Wasserstein policies perform strongly across sample sizes.
- Approximation Quality: The experiments compare the C0 copositive approximation and a quadratic decision-rule approximation against exact worst-case expectations over 2-Wasserstein balls.The exact benchmark is computed with an SOCP, while both approximations are evaluated on randomly generated instances.
- Approximation Quality: The exact worst-case expectation can be represented by an SOCP with O(2N2) constraints, although its size may be exponential in the uncertainty dimension.The SOCP construction uses auxiliary epigraph variables and second-order-cone reformulations.
- Approximation Quality: For K = 64, C0 approximation instances encounter numerical difficulties because semidefinite blocks reach 139×139, while MOSEK solves all quadratic decision-rule instances.The reported computational boundary concerns solving larger C0 instances to global optimality.
A E-Companion: Proof of Theorem 1
The proof represents the Wasserstein worst-case expectation through a generalized moment problem and its semi-infinite dual. Strong duality establishes equality between the resulting dual value and the worst-case expectation, including the unbounded case.
- Generalized Moment Reformulation: The Wasserstein transportation plan is decomposed into conditional distributions, converting the worst-case expectation into a generalized moment problem.The joint distribution couples the uncertain variable with the empirical distribution, and conditional laws are indexed by the empirical samples.
- Strong Duality: The generalized moment problem and its semi-infinite linear-programming dual have equal optimal values when the recourse cost is finite everywhere.Strong duality holds for all ϵ > 0 under the stated conditions.
- Unbounded Case: If the recourse cost is infinite at some scenario, the primal problem is unbounded and the dual is infeasible.A feasible mixture placing positive mass on that scenario yields infinite worst-case expectation.
- Conclusion: Consequently, the dual optimal value coincides with the worst-case expectation in both the finite and unbounded cases.This completes the proof of the Wasserstein dual representation.