×

Distribution functions, extremal limits and optimal transport. (English) Zbl 1334.90145

Let \(c(x,y)\) be a cost function and \(C(x,y)\) be a copula. This paper is an expository paper on different types of optimizations, namely: (1) Find extremes of \(\frac{1}{N}\sum_{n=1}^Nc(x_n,y_n)\) over uniformly distributed sequences \(x_n\) and \(y_n\). (2) For \(\int_0^1\int_0^1c(x,y)dC(x,y)\) find optimal bounds with respect to \(C(x,y)\). (3) General theory of Monge-Kantorovich transport problem and problems from risk management.
In these directions the authors present some known theorems, we mention here three results:
(I) Let a cost function \(c(x,y)\) be a Riemann integrable and assume that \(d_x d_y c(x,y)>0\) for \((x,y)\in(0,1)^2\). Then \[ \max_{C(x,y)\text{-copula}}\int_0^1\int_0^1c(x,y)d_xd_yC(x,y) =\int_0^1c(x,x)d x, \]
\[ \min_{C(x,y)\text{-copula}}\int_0^1\int_0^1c(x,y)d_xd_yC(x,y) =\int_0^1c(x,1-x)d x, \] where the \(\max\) is attained in \(C(x,y)=\min(x,y)\) and \(\min\) in \(C(x,y)=\max(x+y-1,0)\), uniquely.
(II) L. Uckelmann [in: Distributions with given marginals and moment problems. Proceedings of the 1996 conference, Prague, Czech Republic. Dordrecht: Kluwer Academic Publishers. 275–281 (1997; Zbl 0907.60022)] established: Let \(c(x,y)=\Phi(x+y)\) for \((x,y)\in[0,1]^2\); For \(0<k_1<k_2<2\) let \(\Phi(x)\) be a twice differentiable function such that \(\Phi(x)\) is strictly convex on \([0,k_1]\cup[k_2,2]\) and concave on \([k_1,k_2]\). If \(\alpha\) and \(\beta\) are the solutions of \[ \Phi(2\alpha)-\Phi(\alpha+\beta)+(\beta-\alpha)\Phi'(\alpha+\beta)=0, \]
\[ \Phi(2\beta)-\Phi(\alpha+\beta)+(\alpha-\beta)\Phi'(\alpha+\beta)=0 \] such that \(0<\alpha<\beta<1\), then the optimal copula \(C(x,y)\) is attained at the shuffle of \(M\) with the support \(\Gamma(x)\), where \(\Gamma(x)=x\) for \(x\in[0,\alpha]\cup[\beta,1]\), and \(\Gamma(x)=\alpha+\beta-x\) for \(x\in(\alpha,\beta)\). The authors use this result for solving sine problem \(c(x,y)=\sin(\pi(x+y))\) in Problem 1.29 [https://math.boku.ac.at/udt/unsolvedproblems.pdf].
(III) Approximated the cost function \(c(x,y)\) by piecewise constant functions M. Hofer and M. R. Iacò [J. Optim. Theory Appl. 161, No. 3, 999–1011 (2014; Zbl 1293.90036)] proved: Let \((a_{i,j})\), \(i,j=1,2,\dots,n\) be a real-valued \(n\times n\) matrix. Let \(I_{i,j}=\big[\frac{i-1}{n},\frac{i}{n}\big]\times\big[\frac{j-1}{n},\frac{j}{n}\big]\), \(i,j=1,2,\dots,n\) and let the piecewise constant function \(c(x,y)\) be defined as \(c(x,y)=a_{i,j}\text{ if }(x,y)\in I_{i,j}, i,j=1,2,\dots,n.\) Then \[ \max_{C(x,y)\text{-copula}}\int_0^1\int_0^1c(x,y)d_xd_yC(x,y) =\frac{1}{n}\sum_{i=1}^na_{i,\pi^*(i)}. \] Here \(\pi^*(i)\) maximizes \(\sum_{i=1}^na_{i,\pi(i)}\), where \(\pi\) is a permutation of \((1,2,\dots,n)\). finally, the authors use this method, to approximate solution of \(c(x,y)=\sin(\pi x)\sin(\pi y)\), \(c(x,y)=\sin(\pi x)\cos(\pi y)\) and \(c(x,y)=\sin(\pi/x)\cos(2\pi y)\), respectively. The exact values of optimal \(C(x,y)\) are open.

MSC:

90C27 Combinatorial optimization
60E05 Probability distributions: general theory
90C46 Optimality conditions and duality in mathematical programming

Software:

QRM
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aistleitner, C.; Hofer, M., On the limit distribution of consecutive elements of the van der corput sequence, Unif. Distrib. Theory, 8, 1, 89-96 (2013) · Zbl 1340.11060
[2] Ambrosio, L.; Gigli, N., A user’s guide to optimal transport, (Modelling and Optimisation of Flows on Networks. Modelling and Optimisation of Flows on Networks, Lecture Notes in Math., vol. 2062 (2013), Springer: Springer Heidelberg), 1-155
[3] Ambrosio, L.; Gigli, N.; Savaré, G., (Gradient Flows in Metric Spaces and in the Space of Probability Measures. Gradient Flows in Metric Spaces and in the Space of Probability Measures, Lectures in Mathematics ETH Zürich (2008), Birkhäuser Verlag: Birkhäuser Verlag Basel) · Zbl 1145.35001
[5] Baláž, V.; Mišík, L.; Strauch, O.; Tóth, J. T., Distribution functions of ratio sequences, III, Publ. Math. Debrecen, 82, 3-4, 511-529 (2013) · Zbl 1274.11118
[6] Baláž, V.; Mišík, L.; Strauch, O.; Tóth, J. T., Distribution functions of ratio sequences, IV, Period. Math. Hungar., 66, 1, 1-22 (2013) · Zbl 1274.11119
[7] Beiglböck, M.; Henry-Labordère, P.; Penkner, F., Model-independent bounds for option prices—a mass transport approach, Finance Stoch., 17, 3, 477-501 (2013) · Zbl 1277.91162
[8] Beiglböck, M.; Léonard, C.; Schachermayer, W., A general duality theorem for the Monge-Kantorovich transport problem, Studia Math., 209, 2, 151-167 (2012) · Zbl 1270.49045
[9] Beiglböck, M.; Léonard, C.; Schachermayer, W., On the duality theory for the Monge-Kantorovich transport problem, (Ollivier, Y.; Pajot, H.; Villani, C., Optimal Transportation (2014), Cambridge University Press), 216-265, Cambridge Books Online · Zbl 1333.49064
[10] Beiglböck, M.; Schachermayer, W., Duality for Borel measurable cost functions, Trans. Amer. Math. Soc., 363, 8, 4203-4224 (2011) · Zbl 1228.49046
[11] Bernard, C.; Jiang, X.; Wang, R., Risk aggregation with dependence uncertainty, Insurance Math. Econom., 54, 93-108 (2014) · Zbl 1291.91090
[12] Brenier, Y., Décomposition polaire et réarrangement monotone des champs de vecteurs, C. R. Acad. Sci., Paris I, 305, 19, 805-808 (1987) · Zbl 0652.26017
[13] Burkard, R.; Dell’Amico, M.; Martello, S., Assignment Problems (2009), Society for Industrial and Applied Mathematics (SIAM): Society for Industrial and Applied Mathematics (SIAM) Philadelphia, PA · Zbl 1196.90002
[14] Carlier, G., A general existence result for the principal-agent problem with adverse selection, J. Math. Econom., 35, 1, 129-150 (2001) · Zbl 0972.91068
[15] Carlier, G.; Ekeland, I., Equilibrium structure of a bidimensional asymmetric city, Nonlinear Anal. RWA, 8, 3, 725-748 (2007) · Zbl 1136.91023
[16] Çela, E., (The Quadratic Assignment Problem, Theory and Algorithms. The Quadratic Assignment Problem, Theory and Algorithms, Combinatorial Optimization, vol. 1 (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht) · Zbl 0909.90226
[17] de Amo, E.; Díaz Carrillo, M.; Fernández-Sánchez, J., Measure-preserving functions and the independence copula, Mediterr. J. Math., 8, 3, 431-450 (2011) · Zbl 1242.62042
[18] Drmota, M.; Tichy, R. F., (Sequences, Discrepancies and Applications. Sequences, Discrepancies and Applications, Lecture Notes in Mathematics, vol. 1651 (1997), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0877.11043
[19] Durante, F.; Sánchez, J. F., On the approximation of copulas via shuffles of Min, Statist. Probab. Lett., 82, 10, 1761-1767 (2012) · Zbl 1349.62174
[20] Durante, F.; Sarkoci, P.; Sempi, C., Shuffles of copulas, J. Math. Anal. Appl., 352, 2, 914-921 (2009) · Zbl 1160.60307
[21] Durante, F.; Sempi, C., Principles of Copula Theory (2015), CRC/Chapman & Hall: CRC/Chapman & Hall London
[22] Fialová, J.; Mišk, L.; Strauch, O., An asymptotic distribution function of the three-dimensional shifted van der corput sequence, Appl. Math., 5, 15, 2334 (2014)
[23] Fialová, J.; Strauch, O., On two-dimensional sequences composed by one-dimensional uniformly distributed sequences, Unif. Distrib. Theory, 6, 1, 101-125 (2011) · Zbl 1313.11089
[24] Grekos, G.; Strauch, O., Distribution functions of ratio sequences. II, Unif. Distrib. Theory, 2, 1, 53-77 (2007) · Zbl 1183.11042
[25] Hofer, M.; Iacò, M. R., Optimal bounds for integrals with respect to copulas and applications, J. Optim. Theory Appl., 161, 3, 999-1011 (2014) · Zbl 1293.90036
[26] Joe, H., (Multivariate Models and Dependence Concepts. Multivariate Models and Dependence Concepts, Monographs on Statistics and Applied Probability, vol. 73 (1997), Chapman & Hall: Chapman & Hall London) · Zbl 0990.62517
[27] Kallenberg, O., (Foundations of Modern Probability. Foundations of Modern Probability, Probability and its Applications (New York) (2002), Springer-Verlag: Springer-Verlag New York) · Zbl 0996.60001
[28] Kuhn, H. W., Statement for Naval Research Logistics: “The Hungarian method for the assignment problem”, Naval Res. Logist., 52, 1, 6-21 (2005), Reprinted from Naval Res. Logist. Quart. 2 (1955), 83-97 [MR0075510] · Zbl 1154.90301
[29] Lott, J.; Villani, C., Ricci curvature for metric-measure spaces via optimal transport, Ann. of Math. (2), 169, 3, 903-991 (2009) · Zbl 1178.53038
[30] McNeil, A. J.; Frey, R.; Embrechts, P., (Quantitative Risk Management, Concepts, Techniques and Tools. Quantitative Risk Management, Concepts, Techniques and Tools, Princeton Series in Finance (2005), Princeton University Press: Princeton University Press Princeton, NJ) · Zbl 1089.91037
[31] Mikusiński, P.; Sherwood, H.; Taylor, M. D., Shuffles of min, Stochastica, 13, 1, 61-74 (1992) · Zbl 0768.60017
[32] Munkres, J., Algorithms for the assignment and transportation problems, J. Soc. Ind. Appl. Math., 5, 32-38 (1957) · Zbl 0083.15302
[33] Nelsen, R. B., (An Introduction to Copulas. An Introduction to Copulas, Springer Series in Statistics (2006), Springer: Springer New York) · Zbl 1152.62030
[34] Nguyen, D. M.; Le Thi, H. A.; Pham Dinh, T., Solving the multidimensional assignment problem by a cross-entropy method, J. Comb. Optim., 27, 4, 808-823 (2014) · Zbl 1297.90072
[35] Pillichshammer, F.; Steinerberger, S., Average distance between consecutive points of uniformly distributed sequences, Unif. Distrib. Theory, 4, 1, 51-67 (2009) · Zbl 1208.11088
[36] Puccetti, G.; Rüschendorf, L., Sharp bounds for sums of dependent risks, J. Appl. Probab., 50, 1, 42-53 (2013) · Zbl 1282.60017
[37] Rachev, S. T.; Rüschendorf, L., (Mass Transportation Problems. Vol. I, Theory. Mass Transportation Problems. Vol. I, Theory, Probability and its Applications (New York) (1998), Springer-Verlag: Springer-Verlag New York) · Zbl 0990.60500
[38] Rochet, J.-C., A necessary and sufficient condition for rationalizability in a quasilinear context, J. Math. Econom., 16, 2, 191-200 (1987) · Zbl 0628.90003
[39] Rüschendorf, L., Monge-Kantorovich transportation problem and optimal couplings, Jahresber. Deutsch. Math.-Verein., 109, 3, 113-137 (2007) · Zbl 1132.60019
[40] Rüschendorf, L., (Mathematical Risk Analysis, Dependence, Risk Bounds, Optimal Allocations and Portfolios. Mathematical Risk Analysis, Dependence, Risk Bounds, Optimal Allocations and Portfolios, Springer Series in Operations Research and Financial Engineering (2013), Springer: Springer Heidelberg) · Zbl 1266.91001
[41] Rüschendorf, L.; Uckelmann, L., Numerical and analytical results for the transportation problem of Monge-Kantorovich, Metrika, 51, 3, 245-258 (2000), (electronic) · Zbl 1016.60017
[42] Schachermayer, W.; Teichmann, J., Characterization of optimal transport plans for the Monge-Kantorovich problem, Proc. Amer. Math. Soc., 137, 2, 519-529 (2009) · Zbl 1165.49015
[43] Strauch, O., Unsolved problems, Tatra Mt. Math. Publ., 56, 109-229 (2013) · Zbl 1309.11006
[44] Strauch, O.; Tóth, J. T., Distribution functions of ratio sequences, Publ. Math. Debrecen, 58, 4, 751-778 (2001) · Zbl 0980.11031
[45] Tichy, R. F.; Winkler, R., Uniform distribution preserving mappings, Acta Arith., 60, 2, 177-189 (1991) · Zbl 0708.11034
[46] Uckelmann, L., Optimal couplings between one-dimensional distributions, (Distributions with Given Marginals and Moment Problems (Prague, 1996) (1997), Kluwer Acad. Publ.: Kluwer Acad. Publ. Dordrecht), 275-281 · Zbl 0907.60022
[47] van der Corput, J. G., Verteilungsfunktionen I-II, Proc. Akad. Amst., 38, 813-821 (1935), 1058-1066 · Zbl 0012.34705
[48] van der Corput, J. G., Verteilungsfunktionen III-VIII, Proc. Akad. Amst., 39, 10-19 (1936), 19-26, 149-153, 339-344, 489-494, 579-590 · Zbl 0013.16001
[49] Villani, C., (Optimal Transport, Old and New. Optimal Transport, Old and New, Grundlehren der Mathematischen Wissenschaften, vol. 338 (2009), Springer-Verlag: Springer-Verlag Berlin) · Zbl 1156.53003
[50] Xia, Q., The formation of a tree leaf, ESAIM Control Optim. Calc. Var., 13, 2, 359-377 (2007), (electronic) · Zbl 1114.92048
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.