×

The geometry of optimal transportation. (English) Zbl 0887.49017

This paper treats a classical (1781) problem of Monge whose essence is: Let \((X,\mu)\) and \((Y,\nu)\) be (probability) measure spaces, where \(\mu\) represents the distribution of the production of some commodity at various “localities” \(x\in X\) and \(\nu\) of the consumption of that commodity at localities \(y\in Y\). There is a cost function \(c(x,y)\) on \(X\times Y\) which represents the cost of transporting the commodity from \(x\) to \(y\). A measure-preserving transformation \(s:X\to Y\) represents a “distribution scheme” for the commodity, resulting in a total transport cost of \(C_1(s)= \int c(x,s(x))d\mu(x)\). Monge’s problem is to find, where possible, the (or an) \(s\) which gives the minimum \(M_1\) of \(C_1(s)\) over all such choices of \(s\). Kantorovich’s problem, simpler than Monge’s one, is to find, where possible, a measure \(\gamma\) on \(X\times Y\) which has \(\mu\) and \(\nu\) as marginals, and which gives the minimum \(M_2\) of the transport cost \(C_2(\gamma)= \int c(x,y)d\gamma(x, y)\) over all such choices of \(\gamma\).
It is easy to see that \(M_2\leq M_1\), but there are cases where \(M_1= M_2\) and where \(s\) can be accessed through \(\gamma\). Sometimes \(s\) is even uniquely determined a.e. For their main (positive) results, the authors restrict themselves to \(X, Y\subseteq\mathbb{R}^d\), \(d= 1,2,3,\dots\), and to two classes of cost functions: (i) \(c(x,y)= h(x-y)\), where \(h\) is strictly convex (relatively easy); (ii) \(c(x,y)= l(|x-y|)\), where \(|\cdot|\) denotes Euclidean distance on \(\mathbb{R}^d\), and where \(l\geq 0\) is strictly concave (harder but more realistic in the economic context). They also give numerous examples where the (unique) map \(s\) can be explicitly constructed, and their treatment is largely self-contained.

MSC:

49J99 Existence theories in calculus of variations and optimal control
91B60 Trade models
90B06 Transportation, logistics and supply chain management
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdellaoui, T., Détermination d’un couple optimal du problème de Monge-Kantorovitch.C. R. Acad. Sci. Paris Sér. I Math., 319 (1994), 981–984. · Zbl 0809.60003
[2] Abdellaoui, T. &Heinich, H., Sur la distance de deux lois dans le cas vectoriel.C. R. Acad. Sci. Paris Sér. I Math., 319 (1994), 397–400. · Zbl 0808.60008
[3] Alberti, G., On the structure of singular sets of convex functions.Calc. Var. Partial Differential Equations, 2 (1994), 17–27. · Zbl 0790.26010
[4] Aleksandrov, A. D., Existence and uniqueness of a convex surface with a given integral curvature.C. R. (Doklady) Acad. Sci. URSS (N.S.), 35 (1942), 131–134. · Zbl 0061.37604
[5] Appell, P., Memoire sur les déblais et les remblais des systèmes continues ou discontinues.Mémoires présentés par divers Savants à l’Académie des Sciences de l’Institut de France, Paris, I. N., 29 (1887), 1–208.
[6] Balder, E. J., An extension of duality-stability relations to non-convex optimization problems.SIAM J. Control Optim. 15 (1977), 329–343. · Zbl 0366.90103
[7] Brenier, Y., Decomposition polaire et réarrangement monotone des champs de vecteurs.C. R. Acad. Sci. Paris Sér. I Math. 305 (1987), 805–808. · Zbl 0652.26017
[8] –, Polar factorization and monotone rearrangement of vector-valued functions.Comm. Pure Appl. Math., 44 (1991), 375–417. · Zbl 0738.46011
[9] Caffarelli, L., The regularity of mappings with a convex potential.J. Amer. Math. Soc., 5 (1992), 99–104. · Zbl 0753.35031
[10] –, Allocation maps with general cost functions, inPartial Differential Equations and Applications (P. Marcellini, G. Talenti and E. Vesintini, eds.), pp. 29–35. Lecture Notes in Pure and Appl. Math., 177. Dekker, New York, 1996.
[11] Cuesta-Albertos, J. A. &Matrán, C., Notes on the Wasserstein metric in Hilbert spaces.Ann. Probab., 17 (1989), 1264–1276. · Zbl 0688.60011
[12] Cuesta-Albertos, J. A., Matrán, C. & Tuero-Díaz, A., Properties of the optimal maps for theL 2-Monge-Kantorovich transportation problem. Preprint. · Zbl 0892.60020
[13] Cuesta-Albertos, J. A., Rüschendorf, L. &Tuero-Díaz, A., Optimal coupling of multivariate distributions and stochastic processes.J. Multivariate Anal., 46 (1993), 335–361. · Zbl 0788.60025
[14] Cuesta-Albertos, J. A. &Tuero-Díaz, A., A characterization for the solution of the Monge-Kantorovich mass transference problem.Statist. Probab. Lett., 16 (1993), 147–152. · Zbl 0765.60010
[15] Dall’Aglio, G., Sugli estremi dei momenti delle funzioni di ripartizione-doppia.Ann. Scuola Norm. Sup. Pisa Cl. Sci. (3), 10 (1956), 35–74. · Zbl 0073.14002
[16] Darboux, G., Prix Bordin (géométrie).C. R. Acad. Sci. Paris, 101 (1885), 1312–1316.
[17] Douglis, A., Solutions in the large for multi-dimensional non-linear partial differential equations of first order.Ann. Inst. Fourier (Grenoble), 15:2 (1965), 1–35. · Zbl 0137.29001
[18] Evans, L. C. & Gangbo, W., Differential equations methods for the Monge-Kantorovich mass transfer problem. Preprint. · Zbl 0920.49004
[19] Fréchet, M., Sur la distance de deux lois de probabilité.C. R. Acad. Sci. Paris, 244 (1957), 689–692. · Zbl 0077.33007
[20] Gangbo, W. &McCann, R. J., Optimal maps in Monge’s mass transport problem.C. R. Acad. Sci. Paris Sér. I Math., 321 (1995), 1653–1658. · Zbl 0858.49002
[21] Kantorovich, L., On the translocation of masses.C. R. (Doklady) Acad. Sci. URSS (N. S.), 37 (1942), 199–201. · Zbl 0061.09705
[22] –, On a problem of Monge.Uspekhi Mat. Nauk. 3 (1948), 225–226 (in Russian).
[23] Katz, B. S. (editor),Nobel Laureates in Economic Sciences: A Biographical Dictionary. Garland Publishing Inc., New York, 1989.
[24] Kellerer, H. G., Duality theorems for marginal problems.Z. Wahrsch. Verw. Gebiete, 67 (1984), 399–432. · Zbl 0535.60002
[25] Knott, M. &Smith, C. S., On the optimal mapping of distributions.J. Optim. Theory Appl., 43 (1984), 39–49. · Zbl 0519.60010
[26] Levin, V. L., General Monge-Kantorovich problem and its applications in measure theory and mathematical economics, inFunctional Analysis, Optimization, and Mathematical Economics (L. J. Leifman, ed.), pp. 141–176. Oxford Univ. Press, New York, 1990. · Zbl 0989.49500
[27] McCann, R. J., Existence and uniqueness of monotone measure-preserving maps.Duke Math. J., 80 (1995), 309–323. · Zbl 0873.28009
[28] McCann, R. J., A convexity principle for interacting gases. To appear inAdv. in Math. · Zbl 0901.49012
[29] McCann, R. J., Exact solutions to the transportation problem on the line. To appear. · Zbl 0947.90010
[30] Monge, G., Mémoire sur la théorie des déblais et de remblais.Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année, 1781, pp. 666–704.
[31] Rachev, S. T., The Monge-Kantorovich mass transference problem and its stochastic applications.Theory Probab. Appl., 29 (1984), 647–676. · Zbl 0581.60010
[32] Rockafellar, R. T., Characterization of the subdifferentials of convex functions.Pacific J. Math., 17 (1966), 497–510. · Zbl 0145.15901
[33] –,Convex Analysis. Princeton Univ. Press, Princeton, NJ, 1972. · Zbl 0259.90023
[34] Rüschendorf, L., Bounds for distributions with multivariate marginals, inStochastic Orders and Decision Under Risk (K. Mosler and M. Scarsini, eds.), pp. 285–310. IMS Lecture Notes-Monograph Series. Inst. of Math. Statist, Hayward, CA, 1991. · Zbl 0760.60019
[35] –, Frechet bounds and their applications, inAdvances in Probability Distributions with Given Marginals (G. Dall’Aglio et al., eds.), pp. 151–187. Math. Appl., 67. Kluwer Acad. Publ., Dordrecht, 1991.
[36] –, Optimal solutions of multivariate coupling problems.Appl. Math. (Warszaw), 23 (1995), 325–338. · Zbl 0844.62047
[37] –, Onc-optimal random variables.Statist. Probab. Lett., 27 (1996), 267–270. · Zbl 0847.62046
[38] Rüschendorf, L. &Rachev, S. T., A characterization of random variables with minimumL 2-distance.J. Multivariate Anal., 32 (1990), 48–54. · Zbl 0688.62034
[39] Schneider, R.,Convex Bodies: The Brunn-Minkowski Theory. Cambridge Univ. Press, Cambridge, 1993. · Zbl 0798.52001
[40] Smith, C. &Knott, M., On the optimal transportation of distributions.J. Optim. Theory Appl., 52 (1987), 323–329. · Zbl 0586.49005
[41] –, On Hoeffding-Fréchet bounds and cyclic monotone relations.J. Multivariate Anal., 40 (1992), 328–334. · Zbl 0745.62055
[42] Sudakov, V. N., Geometric problems in the theory of infinite-dimensional probability distributions.Proc. Steklov Inst. Math., 141 (1979), 1–178.
[43] Zajíĉek, L., On the differentiation of convex functions in finite and infinite dimensional spaces.Czechoslovak Math. J. 29 (104) (1979), 340–348.
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.