Remarks on the Monge–Kantorovich problem in the discrete setting

Haïm Brezis

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

Haïm Brezis ^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, Volume 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 :

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

@article{CRMATH_2018__356_2_207_0,
     author = {Ha{\"\i}m Brezis},
     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},
}

TY  - JOUR
AU  - Haïm Brezis
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
DO  - 10.1016/j.crma.2017.12.008
LA  - en
ID  - CRMATH_2018__356_2_207_0
ER  -

%0 Journal Article
%A Haïm Brezis
%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
%R 10.1016/j.crma.2017.12.008
%G en
%F CRMATH_2018__356_2_207_0

Haïm Brezis. Remarks on the Monge–Kantorovich problem in the discrete setting. Comptes Rendus. Mathématique, Volume 356 (2018) no. 2, pp. 207-213. doi : 10.1016/j.crma.2017.12.008. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2017.12.008/

Bibliographie
Cité par

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

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

[3] L. Ambrosio; N. Gigli 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] M. Beiglböck Cyclical monotonicity and the ergodic theorem, Ergod. Theory Dyn. Syst., Volume 35 (2015), pp. 710-713

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

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

[7] V.I. Bogachev; A.V. Kolesnikov 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] J. Bourgain; H. Brezis; P. Mironescu $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] H. Brezis Liquid crystals and energy estimates for $S^{2}$ -valued maps (J. Ericksen; D. Kinderlehrer, 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] H. Brezis Functional Analysis, Sobolev Spaces and PDEs, Springer, 2011

[11] H. Brezis; J.-M. Coron; E. Lieb 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] H. Brezis; P. Mironescu; I. Shafrir Distances between classes in $W^{1, 1} (Ω; S^{1})$ , Calc. Var. Partial Differ. Equ. (2017) (to appear) | DOI

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

[15] L.C. Evans Partial differential equations and Monge–Kantorovich mass transfer (S.T. Yau, 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] L.C. Evans; W. Gangbo Differential equations methods for the Monge–Kantorovich mass transfer problem, Mem. Amer. Math. Soc., Volume 137 (1999)

[17] W. Gangbo; R. McCann 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] L.V. Kantorovitch 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] L.V. Kantorovitch On a problem of Monge, Usp. Mat. Nauk, Volume 3 (1948), pp. 225-226 (English translation: J. Math. Sci., 133, 2006, pp. 1383)

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

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

[23] R.J. McCann; N. Guillen Five lectures on optimal transportation: geometry, regularity and applications (G. Dafni 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] S. Rachev; L. Rüschendorf Mass Transportation Problems, Springer, 1998

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

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

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

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

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

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

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

[32] A.M. Vershik 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] A.M. Vershik Long history of the Monge–Kantorovich transportation problem, Math. Intell., Volume 35 (2013), pp. 1-9

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

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

[36] J. von Neumann 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 :

Commentaires - Politique

Ces articles pourraient vous intéresser

Intrinsic Sparsity of Kantorovich solutions

Bamdad Hosseini; Stefan Steinerberger

C. R. Math (2022)

On optimality of c-cyclically monotone transference plans

Stefano Bianchini; Laura Caravenna

C. R. Math (2010)

The Plateau problem from the perspective of optimal transport

Haim Brezis; Petru Mironescu

C. R. Math (2019)