Orateur
Description
Distributionally robust optimization is used to solve decision making problems under uncertainty where the distribution of the uncertain data is itself ambiguous. While several tractable models have been proposed for continuous uncertainty using a convex ambiguity set, fewer results are known for discrete uncertainty. In this work, we identify a class of distributionally robust optimization problems with discrete uncertainty that are solvable in polynomial time by viewing it through the lens of submodularity. Towards this, we define a submodular ambiguity set which specifies upper bounds on the expected values of a finite set of submodular functions of the random vector. With univariate and bivariate discrete random variables, we develop a polynomial sized linear program to solve the problem of computing the sharpest upper bound on the expectation of the maximum of affine functions over this ambiguity set. We showcase the modeling power of the submodular ambiguity set by considering upper bounds on the Wasserstein distances between pairs of random variables while incorporating univariate marginal information and demonstrating the breadth of correlations that can be accommodated. Even with continuous uncertainty, this ambiguity set can incorporate information on the random variables that goes beyond existing models at the expense of implementing pseudo-polynomial time algorithms. Our results show that the submodular ambiguity set supplements the convex ambiguity set, both in terms of modeling and computation.
