  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 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 with given univariate marginal
distributions and bivariate marginals satisfying specific positive dependence
orders along with an extension to incorporate higher order marginal
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 the
bounds improve by 2 to 8 percent over bounds that use only univariate
information in the first case, and by 8 to 15 percent over bounds that use the
first moment in the second case.

Optimization and Control