Distributionally Robust Linear and Discrete Optimization with Marginals

Thursday, October 4, 2018 - 2:45pm - 3:30pm
Keller 3-180
Karthik Natarajan (Singapore University of Technology and Design)
In this work, we study the class of linear and discrete optimization problems in which the objective coefficients are chosen randomly from a distribution, and the goal is to evaluate robust bounds on the expected optimal value as well as the marginal distribution of the optimal solution. The set of joint distributions is assumed to be specified up to only the marginal distributions. We generalize the primal-dual formulations for this problem from the set of joint distributions with absolutely continuous marginal distributions to arbitrary marginal distributions using techniques from optimal transport theory. While the robust bound is NP-hard to compute for linear optimization problems, we identify sufficient conditions for polynomial time solvability. We discuss applications of this approach to distributionally robust optimization. This talk is based on joint work with Louis Chen (MIT), Will Ma (MIT), David Simchi-Levi (MIT), James Orlin (MIT) and Zhenzhen Yan (NTU).