Distributions with Maximum Spread Subject to Wasserstein Distance Constraints

doi:10.1007/s40305-018-00238-5

Abstract

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.

Key words: Distributionally robust optimization, Surveillance, Districting

John Gunnar Carlsson, Ye Wang. Distributions with Maximum Spread Subject to Wasserstein Distance Constraints[J]. Journal of the Operations Research Society of China, 2019, 7(1): 69-106.

TrendMD

References

[1] Delage, E., Ye, Y.:Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3), 595-612(2010)
[2] Goh, J., Sim, M.:Distributionally robust optimization and its tractable approximations. Oper. Res. 58(4-part-1), 902-917(2010)
[3] Calafiore, G.C.:Ambiguous risk measures and optimal robust portfolios. SIAM J. Optim. 18(3), 853-877(2007)
[4] Klabjan, D., Simchi-Levi, D., Song, M.:Robust stochastic lot-sizing by means of histograms. Prod. Oper. Manag. 22(3), 691-710(2013)
[5] Ben-Tal, A., Den Hertog, D., De Waegenaere, A., Melenberg, B., Rennen, G.:Robust solutions of optimization problems affected by uncertain probabilities. Manag. Sci. 59(2), 341-357(2013)
[6] Ben-Tal, A., Bertsimas, D., Brown, D.:A soft robust model for optimization under ambiguity. Oper. Res. 58(4), 1220-1234(2010)
[7] Carlsson, J.G., Devulapalli, R.:Dividing a territory among several facilities. INFORMS J. Comput. 25(4), 730-742(2012). Accessed 1 Apr 2018
[8] Jaynes, E.T.:Information theory and statistical mechanics. Phys. Rev. 104(4), 620-630(1957)
[9] Hyndman, Rob J.:Computing and graphing highest density regions. Am. Stat. 50(2), 120-126(1996)
[10] Goffin, J.-L., Vial, J.-P.:Convex nondifferentiable optimization:a survey focused on the analytic center cutting plane method. Optim Methods Softw. 17(5), 805-867(2002)
[11] Calafiore, G.C., El Ghaoui, L.:On distributionally robust chance-constrained linear programs. J. Optim. Theory Appl. 130(1), 1-22(2006)
[12] Pavone, M., Savla, K., Frazzoli, E.:Sharing the load. IEEE Robot. Autom. Mag. 16, 52-61(2009)
[13] Xie, W., Ouyang, Y.:Optimal layout of transshipment facility locations on an infinite homogeneous plane. Transp. Res. Part B Methodol. 75, 74-88(2015)
[14] Daganzo, C.:Logistics Systems Analysis. Springer, Berlin (2005)
[15] Halverson, N.:Google claims right to post photos from private land. The Press Democrat (2008)
[16] Popescu, I.:Robust mean-covariance solutions for stochastic optimization. Oper. Res. 55(1), 98-112(2007)
[17] Zymler, S., Kuhn, D., Rustem, B.:Distributionally robust joint chance constraints with second-order moment information. Math. Program. 137(1-2), 167-198(2013)
[18] Chen, X., Sim, M., Sun, P.:A robust optimization perspective on stochastic programming. Oper. Res. 55(6), 1058-1071(2007)
[19] Carlsson, J.G., Delage, E.:Robust partitioning for stochastic multivehicle routing. Oper. Res. 61(3), 727-744(2013)
[20] Caillerie, C., Chazal, F., Dedecker, J., Michel, B.:Deconvolution for the Wasserstein metric and geometric inference. In Geometric Science of Information. Springer, pp. 561-568(2013)
[21] Irpino, A., Verde, R.:A new Wasserstein based distance for the hierarchical clustering of histogram symbolic data. In Data Science and Classification. Springer, pp. 185-192(2006)
[22] Pampalk, E., Flexer, A., Widmer, G., et al.:Improvements of audio-based music similarity and genre classification. In ISMIR, vol. 5, pp. 634-637. London, UK (2005)
[23] Rubner, Y., Tomasi, C., Guibas, L.J.:The earth mover's distance as a metric for image retrieval. Int. J. Comput. Vis. 40(2), 99-121(2000)
[24] Erdoǧan, E., Iyengar, G.:Ambiguous chance constrained problems and robust optimization. Math. Program. 107(1-2), 37-61(2006)
[25] Wozabal, D.:A framework for optimization under ambiguity. Ann. Oper. Res. 193(1), 21-47(2012)
[26] Wozabal, D.:Robustifying convex risk measures for linear portfolios:a nonparametric approach. Oper. Res. 62(6), 1302-1315(2014)
[27] Bertsimas, D., Gupta, V., Kallus, N.:Data-driven robust optimization. arXiv preprint arXiv:1401.0212(2013)
[28] Iyengar, G.N.:Robust dynamic programming. Math. Oper. Res. 30(2), 257-280(2005)
[29] Pflug, David Wozabal Georg:Ambiguity in portfolio selection. Quant. Finance 7, 435-442(2007)
[30] Carlsson, J.G., Behroozi, M., Mihic, K.:Wasserstein distance and the distributionally robust TSP. Oper. Res. 66(6), 1603-1624(2018)
[31] Kleywegt, A.J., Gao, R.:Distributionally robust stochastic optimization with Wasserstein distance. arXiv:1604.02199(2016)
[32] Esfahani, P.M., Kuhn, D.:Data-driven distributionally robust optimization using the Wasserstein metric:performance guarantees and tractable reformulations. arXiv:1505.05116(2015)
[33] Murthy, K., Blanchet, J., Kang, Y.:Robust Wasserstein profile inference and applications to machine learning. arXiv:1610.05627(2017)
[34] Luenberger, D.G.:Optimization by Vector Space Methods. Wiley, Hoboken (1968)
[35] Villani, C.:Topics in Optimal Transportation. AMS, Philadelphia (2003)
[36] Amari, S., Karakida, R., Oizumi, M.:Information geometry connecting Wasserstein distance and Kullback-Leibler divergence via the entropy-relaxed transportation problem. Information Geometry, pp. 1-25(2018)
[37] Royden, H.L., Fitzpatrick, P.:Real Analysis, vol. 32. Macmillan, New York (1988)
[38] Dunford, N., Schwartz, J.T.:Linear Operators Part I:General Theory, vol. 7. Interscience Publishers, New York (1958)
[39] Boyd, S.:Localization and cutting-plane methods. http://stanford.edu/class/ee364b/lectures/localization_methods_slides.pdf (2014)
[40] Canas, G., Rosasco, L.:Learning probability measures with respect to optimal transport metrics. In Advances in Neural Information Processing Systems, pp. 2492-2500(2012)
[41] Fournier, N., Guillin, A.:On the rate of convergence in Wasserstein distance of the empirical measure. Probab. Theory Relat. Fields 162(3-4), 707-738(2015)
[42] Villani, C.:Optimal Transport:Old and New, vol. 338. Springer, Berlin (2008)
[43] Bolley, F., Villani, C.:Weighted csiszár-Kullback-Pinsker inequalities and applications to transportation inequalities. Annales de la Faculté des sciences de Toulouse:Mathématiques 14, 331-352(2005)
[44] Bolley, F., Guillin, A., Villani, C.:Quantitative concentration inequalities for empirical measures on non-compact spaces. Probab. Theory Relat. Fields 137(3-4), 541-593(2007)
[45] Krantz, S.G., Parks, H.R.:Geometric Integration Theory. Cornerstones, Birkhäuser (2008)