Distributionally robust optimization is used to solve decision making problems under adversarial uncertainty where the distribution of the uncertainty is itself ambiguous. In this paper, we identify a class of these instances that is solvable in polynomial time by viewing it through the lens of submodularity. We show that the sharpest upper bound on the expectation of the maximum of affine functions of a random vector is computable in polynomial time if each random variable is discrete with finite support and upper bounds (respectively lower bounds) on the expected values of a finite set of submodular (respectively supermodular) functions of the random vector are specified. This adds to the list of known polynomial time solvable instances of the multimarginal optimal transport problem and the generalized moment problem by bridging ideas from convexity in continuous optimization to submodularity in discrete optimization. In turn, we show that a class of distributionally robust optimization problems with discrete random variables is solvable in polynomial time using the ellipsoid method. When the submodular (respectively supermodular) functions are structured, the sharp bound is computable by solving a compact linear program. We illustrate this in two cases. The first is a multimarginal optimal transport problem where the univariate marginal distributions of the discrete random variables are given and the bivariate marginals satisfy specific positive dependence orders. We discuss an extension to incorporate higher order marginal information. Numerical experiments show that the bounds improve by 2 to 8 percent over bounds that use only univariate information. The second is a discrete moment problem where a set of marginal moments of the random variables are given along with lower bounds on the cross moments of pairs of random variables. Numerical experiments show that with higher order marginal moments, the bounds improve by 8 to 15 percent over bounds that use the first moment.
Article
View Distributionally robust optimization through the lens of submodularity