Distributions with Maximum Spread Subject to Wasserstein Distance Constraints
- PDF / 3,899,535 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 62 Downloads / 217 Views
Distributions with Maximum Spread Subject to Wasserstein Distance Constraints John Gunnar Carlsson1 · Ye Wang1 Received: 16 May 2018 / Revised: 26 November 2018 / Accepted: 21 December 2018 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract Recent research on formulating and solving distributionally robust optimization problems has seen many different approaches for describing one’s ambiguity set, such as constraints on first and second moments or quantiles. In this paper, we use the 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. In particular, we derive closed-form expressions for distributions that are as “spread out” as possible, and apply our result to a problem in multi-vehicle coordination. Keywords Distributionally robust optimization · Surveillance · Districting Mathematics Subject Classification 90C15 · 90C34
1 Introduction One of the most complex factors that arises in formulating and solving robust optimization problems is the difficulty of describing one’s ambiguity set in a way that is both useful and mathematically tractable. Recent works have seen many different approaches for describing these sets, such as moment-based approaches [1,2] and statistical distance-based approaches [3–6]. The choice of one’s ambiguity set often yields qualitative insights into what demand patterns affect the outcome most significantly.
This paper is dedicated to Professor Yin-Yu Ye in celebration of his 70th birthday.
B
John Gunnar Carlsson [email protected] Ye Wang [email protected]
1
University of Southern California, Los Angeles, CA 90089-4017, USA
123
J. G. Carlsson, Y. Wang
In this paper, we study a particular problem in distributionally robust optimization in which the ambiguity set is characterized via the Wasserstein distance, which is also known as the earth mover’s distance or Kantorovich metric. Conceptually speaking, the Wasserstein distance is very simple and intuitive: If we visualize two probability distributions μ1 and μ2 as being two piles of equal amounts of sand, then the Wasserstein distance between them is simply the minimum amount of work needed to move one pile to take the shape of the other, as suggested in Fig. 1(a). A particularly attractive
(a)
(b)
(c)
(d)
(e)
(f)
(g)
Fig. 1 (a) Wasserstein distance problem between two univariate distributions μ1 and μ2 . (b)–(d) Wasserstein mapping can be thought of as an infinite-dimensional generalization of a bipartite matching; here, μ1 and μ2 are shown in (b) and (c), and (d) shows a bipartite matching between a large number of samples collected from μ1 and μ2 . (e)–(g) An interpretation of a Wasserstein distance problem when μ1 is a smooth density and μ2 is atomic. The two distributions are shown in (e), and (f) shows the
Data Loading...
