Moment Relaxations for Data-Driven Wasserstein Distributionally Robust Optimization

Abstract

We propose moment relaxations for data-driven $p$-Wasserstein distributionally robust optimization ($p$-WDRO) problems that are defined by polynomials. The proposed moment relaxations admit Benders-type decomposition with parallel evaluation of the subgradients using each sample subproblem, which enables efficient solution for larger training sets. We then identify conditions on $p$ and the defining polynomial degrees such that the proposed $k$-th order moment relaxations preserve the asymptotic consistency of the original $p$-WDRO (i.e., the relaxation gap is bounded at most linearly by the Wasserstein radius). In particular, these conditions translate to effective bounds on $k$, which lead to polynomially sized semidefinite optimization formulations that are compatible with existing solvers. Numerical experiments on a box-constrained regression problem and a two-stage production problem are included to demonstrate the scalability and the effectiveness of the proposed moment relaxations.

arXiv comment38 pages