Numerical resolution of an “unbalanced” mass transport problem
ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 37 (2003) no. 5, pp. 851-868.

We introduce a modification of the Monge-Kantorovitch problem of exponent 2 which accommodates non balanced initial and final densities. The augmented lagrangian numerical method introduced in [6] is adapted to this “unbalanced” problem. We illustrate the usability of this method on an idealized error estimation problem in meteorology.

DOI : https://doi.org/10.1051/m2an:2003058
Classification : 35J60,  65K10,  78A05,  90B99
Mots clés : Monge-Kantorovitch problem, Wasserstein distance, augmented lagrangian method
@article{M2AN_2003__37_5_851_0,
author = {Benamou, Jean-David},
title = {Numerical resolution of an {\textquotedblleft}unbalanced{\textquotedblright} mass transport problem},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis - Mod\'elisation Math\'ematique et Analyse Num\'erique},
pages = {851--868},
publisher = {EDP-Sciences},
volume = {37},
number = {5},
year = {2003},
doi = {10.1051/m2an:2003058},
zbl = {1037.65063},
language = {en},
url = {http://www.numdam.org/articles/10.1051/m2an:2003058/}
}
Benamou, Jean-David. Numerical resolution of an “unbalanced” mass transport problem. ESAIM: Mathematical Modelling and Numerical Analysis - Modélisation Mathématique et Analyse Numérique, Tome 37 (2003) no. 5, pp. 851-868. doi : 10.1051/m2an:2003058. http://www.numdam.org/articles/10.1051/m2an:2003058/

[1] M. Balinski, A competitive (dual) simplex method for the assignment problem. Math. Program. 34 (1986) 125-141. | Zbl 0596.90064

[2] F. Barthe, On a reverse form of the Brascamp-Lieb inequality. Invent. Math. 134 (1998) 335-361. | Zbl 0901.26010

[3] J.-D. Benamou, A domain decomposition method for the polar factorization of vector valued mappings. SIAM J. Numer. Anal. 32 (1995) 1808-1838. | Zbl 0852.65012

[4] J.D. Benamou and Y. Brenier, Numerical resolution on a massively parallel computer of a test problem in meteorology using a domain decomposition algorithm, in First European conference in computational fluid dynamics. North Holland (1992).

[5] J.D. Benamou and Y. Brenier, Weak existence for the semigeostrophic equations formulated as a coupled Monge-Ampère/transport problem. SIAM J. Appl. Math. 58 (1998) 1450-1461. | Zbl 0915.35024

[6] J.D. Benamou and Y. Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84 (2000) 375-393. | Zbl 0968.76069

[7] J.D. Benamou and Y. Brenier, Mixed ${L}^{2}$/Wasserstein Optimal Mapping Between Prescribed Densities Functions (submitted). | Zbl 1010.49029

[8] J.D. Benamou, Y. Brenier and K. Guittet, Numerical resolution of a multiphasic optimal mass transport problem. Tech. Report INRIA RR-4022.

[9] G. Boucjitte, G. Buttazzo and P. Seppechere, Shape Optimization Solutions via Monge-Kantorovich. C. R. Acad. Sci. Paris Sér. I 324 (1997) 1185-1191. | Zbl 0884.49023

[10] Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math. 44 (1991) 375-417. | Zbl 0738.46011

[11] Y. Brenier, Minimal geodesics on groups of volume-preserving maps and generalized solutions of the Euler equations. Comm. Pure Appl. Math. 52 (1999) 411-452. | Zbl 0910.35098

[12] Y. Brenier, Extended Monge-Kantorovich theory. CIME 2001 lecture. | Zbl 1064.49036

[13] L.A. Caffarelli, Boundary regularity of maps with convex potentials. Comm. Pure Appl. Math. 45 (1992) 1141-1151. | Zbl 0778.35015

[14] L.A. Caffarelli, Boundary regularity of maps with convex potentials. II. Ann. of Math. 144 (1996) 3, 453-496. | Zbl 0916.35016

[15] M.J.P. Cullen, Solution to a model of a front forced by deformation. Q. J. R. Met. Soc. 109 (1983) 565-573.

[16] M.J.P. Cullen, private communication.

[17] M.J.P. Cullen and R.J. Purser, An extended Lagrangian theory of semigeostrophic frontogenesis. J. Atmopheric Sci. 41 (1984) 1477-1497.

[18] R.J. Douglas, Decomposition of weather forecast error using rearrangements of functions. (Preprint.)

[19] L.C. Evans, Partial differential equations and Monge-Kantorovich mass transfer. Lecture notes. | Zbl 0954.35011

[20] M. Fortin and R. Glowinski, Augmented Lagrangian methods. Applications to the numerical solution of boundary value problems. North-Holland Publishing Co. Studies in Mathematics and its Applications 15 (1983) 340. | MR 724072 | Zbl 0525.65045

[21] U. Frisch et al., Back to the early Universe by optimal mass transportation. Nature 417 (2002) 260-262.

[22] W. Gangbo and R.J. Mccann, The geometry of optimal transportation. Acta Math. 177 (1996) 113-161. | Zbl 0887.49017

[23] W. Gangbo and R.J. Mccann, Shape recognition via Wasserstein distance. Quart. Appl. Math. 58 (2000) 705-737. | Zbl 1039.49038

[24] K. Guittet, On the time-continuous mass transport problem and its approximation by augmented Lagrangian techniques. SIAM J. Numer. Anal. 41 (2003) 382-399. | Zbl 1039.65050

[25] K. Guittet, Ph.D. dissertation (2002).

[26] S. Haker, A. Tannenbaum and R. Kikinis, Mass preserving mapping and image registration. MICCAI (2001) 120-127. | Zbl 1041.68621

[27] R. Jonker and A. Volgenant, A shortest augmenting path algorithm for dense and sparse linear assignment problem. Computing 38 (1987) 325-340. | Zbl 0607.90056

[28] R. Jordan, D. Kinderlehrer and F. Otto, The variational formulation of the Fokker-Planck equation. SIAM J. Math. Anal. 29 (1998) 1-17. | Zbl 0915.35120

[29] T. Kaijser, Computing the Kantorovich distance for images. J. Math. Imaging Vision 9 (1998) 173-198. | Zbl 0911.68207

[30] L.V. Kantorovich, On the translocation of masses. C. R. (Doklady) Acad. Sci. URSS (N.S.) 37 (1942) 199-201. | Zbl 0061.09705

[31] D. Kinderlehrer and N. Walkington, Approximation of Parabolic Equations based upon a Wasserstein metric. ESAIM: M2AN 33 (1999) 837-852. | Numdam | Zbl 0936.65121

[32] S.A. Kochengin and V.I. Oliker, Determination of reflector surfaces from near-field scattering data. Inverse Problems 13 (1997) 363-373. | Zbl 0871.35107

[33] R.J. Mccann, Polar factorization of maps on Riemannian manifolds. Geom. Funct. Anal. 11 (2001) 589-608. | Zbl 1011.58009

[34] R. Menozzi, Utilisation de la distance de Wasserstein et application sismique. Rapport IUP Génie Mathématique et Informatique, Université Paris IX-Dauphine.

[35] G. Monge, Mémoire sur la théorie des déblais et des remblais. Mem. Acad. Sci. Paris (1781).

[36] F. Otto, The geometry of dissipative evolution equation: the porous medium equation. Comm. Partial Differential Equations 26 (2001) 101-174. | Zbl 0984.35089

[37] S.T. Rachev and L. Rüschendorf, Mass transportation problems, in Theory, Probability and its Applications, Vol. I. Springer-Verlag, New York (1998) 508. | MR 1619170 | Zbl 0990.60500

[38] A. Shnirelman, Generalized fluid flows, their approximation and applications. Geom. Funct. Anal. 4 (1994) 586-620. | Zbl 0851.76003

[39] C. Villani, Topics in mass transport. Lecture notes (2000).