Remarks on the Monge–Kantorovich problem in the discrete setting

Brezis, Haïm

doi:10.1016/j.crma.2017.12.008

Functional analysis/Mathematical analysis

Remarks on the Monge–Kantorovich problem in the discrete setting
[Remarques sur le problème de Monge–Kantorovich dans le cas discret]

Présenté par : Haïm Brezis

Brezis, Haïm ^1,^2,³

¹ Department of Mathematics, Hill Center, Busch Campus, Rutgers University, 110 Frelinghuysen Road, Piscataway, NJ 08854, USA
² Departments of Mathematics and Computer Science, Technion, Israel Institute of Technology, 32000 Haifa, Israel
³ Laboratoire Jacques-Louis-Lions, Université Pierre-et-Marie-Curie, 4, place Jussieu, 75252 Paris cedex 05, France

Comptes Rendus. Mathématique, Tome 356 (2018) no. 2, pp. 207-213.

Résumé
Abstract

En théorie du transport optimal, trois quantités jouent un rôle central : le coût minimal de transport, introduit par Monge, sa version relaxée, introduite par Kantorovich, et la formulation duale, due aussi à Kantorovich. L'objet de cette note est de mettre en avant une démonstration totalement élémentaire, extraite de [9], du fait que ces trois quantités coïncident dans le cas discret ; cette preuve ne requiert aucune connaissance préalable.

In Optimal Transport theory, three quantities play a central role: the minimal cost of transport, originally introduced by Monge, its relaxed version introduced by Kantorovich, and a dual formulation also due to Kantorovich. The goal of this Note is to publicize a very elementary, self-contained argument extracted from [9], which shows that all three quantities coincide in the discrete case.

Reçu le : 2017-12-19
Accepté le : 2017-12-19
Publié le : 2018-01-05

DOI : 10.1016/j.crma.2017.12.008

Affiliations des auteurs :

Brezis, Haïm ^{1, 2, 3}

@article{CRMATH_2018__356_2_207_0,
     author = {Brezis, Ha{\"\i}m},
     title = {Remarks on the {Monge{\textendash}Kantorovich} problem in the discrete setting},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {207--213},
     publisher = {Elsevier},
     volume = {356},
     number = {2},
     year = {2018},
     doi = {10.1016/j.crma.2017.12.008},
     language = {en},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2017.12.008/}
}

TY  - JOUR
AU  - Brezis, Haïm
TI  - Remarks on the Monge–Kantorovich problem in the discrete setting
JO  - Comptes Rendus. Mathématique
PY  - 2018
SP  - 207
EP  - 213
VL  - 356
IS  - 2
PB  - Elsevier
UR  - http://www.numdam.org/articles/10.1016/j.crma.2017.12.008/
DO  - 10.1016/j.crma.2017.12.008
LA  - en
ID  - CRMATH_2018__356_2_207_0
ER  -

%0 Journal Article
%A Brezis, Haïm
%T Remarks on the Monge–Kantorovich problem in the discrete setting
%J Comptes Rendus. Mathématique
%D 2018
%P 207-213
%V 356
%N 2
%I Elsevier
%U http://www.numdam.org/articles/10.1016/j.crma.2017.12.008/
%R 10.1016/j.crma.2017.12.008
%G en
%F CRMATH_2018__356_2_207_0

Brezis, Haïm. Remarks on the Monge–Kantorovich problem in the discrete setting. Comptes Rendus. Mathématique, Tome 356 (2018) no. 2, pp. 207-213. doi : 10.1016/j.crma.2017.12.008. http://www.numdam.org/articles/10.1016/j.crma.2017.12.008/

Bibliographie
Cité par

[1] Afriat, S.N. The system of inequalities $a_{r s} \geq X_{r} - X_{s}$ , Math. Proc. Camb. Philos. Soc., Volume 59 (1963), pp. 125-133

[2] Ambrosio, L. Lecture notes on optimal transport problems (Colli, P.; Rodrigues, J.F., eds.), Mathematical Aspects of Evolving Interfaces, Lect. Notes Math., vol. 1812, Springer, 2003, pp. 1-52

[3] Ambrosio, L.; Gigli, N. A user's guide to optimal transport, Modelling and Optimisation of Flows on Networks, Lect. Notes Math., vol. 2062, Springer, 2013, pp. 1-155

[4] Beiglböck, M. Cyclical monotonicity and the ergodic theorem, Ergod. Theory Dyn. Syst., Volume 35 (2015), pp. 710-713

[5] Bethuel, F.; Brezis, H.; Coron, J.-M. Relaxed energies for harmonic maps (Berestycki, H.; Coron, J.-M.; Ekeland, I., eds.), Variational Problems, Proceedings of a Conference Held in Paris in 1988, Birkhäuser, 1990, pp. 37-52

[6] Birkhoff, G. Tres observaciones sobre el algebra lineal, Rev. Univ. Nac. Tucumán Ser. A, Mat. Fis. Teor., Volume 5 (1946), pp. 147-150

[7] Bogachev, V.I.; Kolesnikov, A.V. The Monge–Kantorovich problem: achievements, connections and perspectives, Usp. Mat. Nauk, Volume 67 (2012), pp. 3-110 (English translation: Russ. Math. Surv., 67, 2012, pp. 785-890)

[8] Bourgain, J.; Brezis, H.; Mironescu, P. $H^{1 / 2}$ maps with values into the circle: minimal connections, lifting, and the Ginzburg–Landau equation, Publ. Math. Inst. Hautes Études Sci., Volume 99 (2004), pp. 1-115

[9] Brezis, H. Liquid crystals and energy estimates for $S^{2}$ -valued maps (Ericksen, J.; Kinderlehrer, D., eds.), Theory and Applications of Liquid Crystals, Proceedings of a Conference Held in Minneapolis, MN, USA, in 1985, Springer, 1987, pp. 31-52 http://sites.math.rutgers.edu/~brezis/publications.html (See also article 112L1 in)

[10] Brezis, H. Functional Analysis, Sobolev Spaces and PDEs, Springer, 2011

[11] Brezis, H.; Coron, J.-M.; Lieb, E. Harmonic maps with defects, Commun. Math. Phys., Volume 107 (1986), pp. 649-705

[12] H. Brezis, P. Mironescu, Sobolev Maps with Values into the Circle, Birkhäuser, in preparation.

[13] Brezis, H.; Mironescu, P.; Shafrir, I. Distances between classes in $W^{1, 1} (Ω; S^{1})$ , Calc. Var. Partial Differ. Equ. (2017) (to appear) | DOI

[14] Burkard, R.; Dell Amico, M.; Martello, S. Assignment Problems, SIAM, 2012

[15] Evans, L.C. Partial differential equations and Monge–Kantorovich mass transfer (Yau, S.T., ed.), Current Developments in Mathematics, Lectures delivered at Harvard in 1997, International Press, Cambridge, MA, USA, 1999, pp. 65-126 https://math.berkeley.edu/evans/ (See also “Survey of applications of PDE methods to Monge–Kantorovich mass transfer problems”)

[16] Evans, L.C.; Gangbo, W. Differential equations methods for the Monge–Kantorovich mass transfer problem, Mem. Amer. Math. Soc., Volume 137 (1999)

[17] Gangbo, W.; McCann, R. The geometry of optimal transportation, Acta Math., Volume 177 (1996), pp. 113-161

[18] Ghys, É. Gaspard Monge. Le mémoire sur les déblais et les remblais, CNRS, Images des mathématiques, 2012 http://images.math.cnrs.fr/Gaspard-Monge,1094.html?lang=fr (See)

[19] Kantorovitch, L.V. On the translocation of masses, Dokl. Akad. Nauk SSSR, Volume 37 (1942), pp. 227-229 (English translation: J. Math. Sci., 133, 2006, pp. 1381-1382)

[20] Kantorovitch, L.V. On a problem of Monge, Usp. Mat. Nauk, Volume 3 (1948), pp. 225-226 (English translation: J. Math. Sci., 133, 2006, pp. 1383)

[21] Knott, M.; Smith, C. On a generalization of cyclic monotonicity and distances among random vectors, Linear Algebra Appl., Volume 199 (1994), pp. 363-371

[22] Linial, N.; Luria, Z. On the vertices of the d-dimensional Birkhoff polytope, Discrete Comput. Geom., Volume 51 (2014), pp. 161-170

[23] McCann, R.J.; Guillen, N. Five lectures on optimal transportation: geometry, regularity and applications (Dafni, G. et al., eds.), Analysis and Geometry of Metric Measure Spaces, Lecture Notes of the “Séminaire de mathématiques supérieures” (SMS), 2011, American Mathematical Society, 2013, pp. 145-180 http://www.math.toronto.edu/mccann/publications (See also [46] in)

[24] Rachev, S.; Rüschendorf, L. Mass Transportation Problems, Springer, 1998

[25] Rochet, J.-C. A necessary and sufficient condition for rationalizability in a quasi-linear context, J. Math. Econ., Volume 16 (1987), pp. 191-200

[26] Rockafellar, R.T. Characterization of the subdifferentials of convex functions, Pac. J. Math., Volume 17 (1966), pp. 497-510

[27] Rüschendorf, L. On c-optimal random variables, Stat. Probab. Lett., Volume 27 (1996), pp. 267-270

[28] Sandier, E. Ginzburg–Landau minimizers from $R^{n + 1}$ to $R^{n}$ and minimal connections, Indiana Univ. Math. J., Volume 50 (2001), pp. 1807-1844

[29] Santambrogio, F. Optimal Transport for Applied Mathematicians, Birkhäuser, 2015

[30] Smith, C.S.; Knott, M. Note on the optimal transportation of distributions, J. Optim. Theory Appl., Volume 52 (1987), pp. 323-329

[31] Smith, C.S.; Knott, M. On Hoeffding–Fréchet bounds and cyclic monotone relations, J. Multivar. Anal., Volume 40 (1992), pp. 328-334

[32] Vershik, A.M. Some remarks on the infinite-dimensional problems of linear programming, Usp. Mat. Nauk, Volume 25 (1970), pp. 117-124 (English translation: Russ. Math. Surv., 25, 1970, pp. 117-124)

[33] Vershik, A.M. Long history of the Monge–Kantorovich transportation problem, Math. Intell., Volume 35 (2013), pp. 1-9

[34] Villani, C. Topics in Optimal Transportation, American Mathematical Society, 2003

[35] Villani, C. Optimal Transport. Old and New, Springer, 2009

[36] von Neumann, J. A certain zero-sum two-person game equivalent to the optimal assignment problem, Contrib. Theory Games, vol. 2, Princeton University Press, Princeton, NJ, USA, 1953, pp. 5-12

Cité par Sources :