×

Distributions with maximum spread subject to Wasserstein distance constraints. (English) Zbl 1424.90196

Summary: 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.

MSC:

90C15 Stochastic programming
90C34 Semi-infinite programming

Software:

EMD; ROME
PDFBibTeX XMLCite
Full Text: DOI

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) · Zbl 1228.90064
[2] Goh, J., Sim, M.: Distributionally robust optimization and its tractable approximations. Oper. Res. 58(4 – part-1), 902-917 (2010) · Zbl 1228.90067
[3] Calafiore, G.C.: Ambiguous risk measures and optimal robust portfolios. SIAM J. Optim. 18(3), 853-877 (2007) · Zbl 1154.91022
[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) · Zbl 1228.90060
[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) · Zbl 0084.43701
[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) · Zbl 1065.90060
[11] Calafiore, G.C., El Ghaoui, L.: On distributionally robust chance-constrained linear programs. J. Optim. Theory Appl. 130(1), 1-22 (2006) · Zbl 1143.90021
[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) · Zbl 0767.90012
[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) · Zbl 1167.90611
[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) · Zbl 1286.90103
[18] Chen, X., Sim, M., Sun, P.: A robust optimization perspective on stochastic programming. Oper. Res. 55(6), 1058-1071 (2007) · Zbl 1167.90608
[19] Carlsson, J.G., Delage, E.: Robust partitioning for stochastic multivehicle routing. Oper. Res. 61(3), 727-744 (2013) · Zbl 1273.90022
[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) · Zbl 1396.94046
[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) · Zbl 1012.68705
[24] Erdoğan, E., Iyengar, G.: Ambiguous chance constrained problems and robust optimization. Math. Program. 107(1-2), 37-61 (2006) · Zbl 1134.90028
[25] Wozabal, D.: A framework for optimization under ambiguity. Ann. Oper. Res. 193(1), 21-47 (2012) · Zbl 1255.91454
[26] Wozabal, D.: Robustifying convex risk measures for linear portfolios: a nonparametric approach. Oper. Res. 62(6), 1302-1315 (2014) · Zbl 1358.91116
[27] Bertsimas, D., Gupta, V., Kallus, N.: Data-driven robust optimization. arXiv preprint arXiv:1401.0212 (2013) · Zbl 1397.90298
[28] Iyengar, G.N.: Robust dynamic programming. Math. Oper. Res. 30(2), 257-280 (2005) · Zbl 1082.90123
[29] Pflug, David Wozabal Georg: Ambiguity in portfolio selection. Quant. Finance 7, 435-442 (2007) · Zbl 1190.91138
[30] Carlsson, J.G., Behroozi, M., Mihic, K.: Wasserstein distance and the distributionally robust TSP. Oper. Res. 66(6), 1603-1624 (2018) · Zbl 1446.90050
[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) · Zbl 1433.90095
[33] Murthy, K., Blanchet, J., Kang, Y.: Robust Wasserstein profile inference and applications to machine learning. arXiv:1610.05627 (2017) · Zbl 1436.62336
[34] Luenberger, D.G.: Optimization by Vector Space Methods. Wiley, Hoboken (1968)
[35] Villani, C.: Topics in Optimal Transportation. AMS, Philadelphia (2003) · Zbl 1106.90001
[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) · Zbl 1409.62020
[37] Royden, H.L., Fitzpatrick, P.: Real Analysis, vol. 32. Macmillan, New York (1988) · Zbl 1191.26002
[38] Dunford, N., Schwartz, J.T.: Linear Operators Part I: General Theory, vol. 7. Interscience Publishers, New York (1958) · Zbl 0084.10402
[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) · Zbl 1325.60042
[42] Villani, C.: Optimal Transport: Old and New, vol. 338. Springer, Berlin (2008) · Zbl 1156.53003
[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) · Zbl 1087.60008
[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) · Zbl 1113.60093
[45] Krantz, S.G., Parks, H.R.: Geometric Integration Theory. Cornerstones, Birkhäuser (2008) · Zbl 1149.28001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.