Applications of Wasserstein distance in distributionally robust optimization

2018-06-26Recent research on formulating and solving distributionally robust optimization problems has seen many different approaches for describing one’s ambiguity set, such as moment based approach and statistical distance based approach. In this dissertation, we use Wasserstein distance to characterize the ambiguity set of distributions, which allows us to circumvent common overestimation that arises when other procedures are used, such as fixing the center of mass and the covariance matrix of the distribution. ❧ We consider distributionally robust versions of the Euclidean travelling salesman problem, the entropy maximization problem and the highest density region optimization problem respectively: as input, we are given a compact, contiguous planar region R and a realization of sampled demand points in that region, and our objective is to construct a probability distribution on R that is sufficiently “close” to the empirical distribution consisting of the sampled points and is as “spread out” as possible, in the sense that the asymptotic length of a TSP tour of points drawn from that distribution should be as large as possible, the entropy of the distribution should be as large as possible, and the coverage probability over the highest density region should be as small as possible. Numerical experiments confirm that our approach is useful when used in a decision support tool for dividing a territory into service districts for a fleet of aerial vehicles when limited data is available