Distributionally Robust Stochastic Optimization with Wasserstein Distance

Rui Gao, Anton J. Kleywegt

Published 2016-04-08Version 1

Stochastic programming is a powerful approach for decision-making under uncertainty. Unfortunately, the solution may be misleading if the underlying distribution of the involved random parameters is not known exactly. In this paper, we study distributionally robust stochastic programming (DRSP) in which the decision hedges against the worst possible distribution that belongs to an ambiguity set, which comprises all distributions that are close to some reference distribution in terms of the Wasserstein distance. We derive a tractable reformulation of the DRSP problem by constructing the worst-case distribution explicitly via the first-order optimality condition of the dual problem. Using the precise structure of the worst-case distribution, we show that the DRSP can be approximated by robust programs to arbitrary accuracy. Then we apply our results to a variety of stochastic optimization problems, including the newsvendor problem, two-stage linear program, worst-case value-at-risk analysis, point processes control and distributionally robust transportation problems.