Numerical resolution of an “unbalanced” mass transport problem

Jean-David Benamou

ESAIM: Mathematical Modelling and Numerical Analysis (2010)

  • Volume: 37, Issue: 5, page 851-868
  • ISSN: 0764-583X

Abstract

top
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.

How to cite

top

Benamou, Jean-David. "Numerical resolution of an “unbalanced” mass transport problem." ESAIM: Mathematical Modelling and Numerical Analysis 37.5 (2010): 851-868. <http://eudml.org/doc/194194>.

@article{Benamou2010,
abstract = { 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. },
author = {Benamou, Jean-David},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis},
keywords = {Monge–Kantorovitch problem; Wasserstein distance; augmented Lagrangian method.; penalization technique; Monge-Kantorovitch problem; augmented Lagrangian numerical method; error estimation; meteorology},
language = {eng},
month = {3},
number = {5},
pages = {851-868},
publisher = {EDP Sciences},
title = {Numerical resolution of an “unbalanced” mass transport problem},
url = {http://eudml.org/doc/194194},
volume = {37},
year = {2010},
}

TY - JOUR
AU - Benamou, Jean-David
TI - Numerical resolution of an “unbalanced” mass transport problem
JO - ESAIM: Mathematical Modelling and Numerical Analysis
DA - 2010/3//
PB - EDP Sciences
VL - 37
IS - 5
SP - 851
EP - 868
AB - 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.
LA - eng
KW - Monge–Kantorovitch problem; Wasserstein distance; augmented Lagrangian method.; penalization technique; Monge-Kantorovitch problem; augmented Lagrangian numerical method; error estimation; meteorology
UR - http://eudml.org/doc/194194
ER -

References

top
  1. M. Balinski, A competitive (dual) simplex method for the assignment problem. Math. Program.34 (1986) 125-141.  
  2. F. Barthe, On a reverse form of the Brascamp-Lieb inequality. Invent. Math.134 (1998) 335-361.  
  3. J.-D. Benamou, A domain decomposition method for the polar factorization of vector valued mappings. SIAM J. Numer. Anal.32 (1995) 1808-1838.  
  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.  
  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.  
  7. J.D. Benamou and Y. Brenier, Mixed L2/Wasserstein Optimal Mapping Between Prescribed Densities Functions (submitted).  
  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. I324 (1997) 1185-1191.  
  10. Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math.44 (1991) 375-417.  
  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.  
  12. Y. Brenier, Extended Monge-Kantorovich theory. CIME 2001 lecture.  
  13. L.A. Caffarelli, Boundary regularity of maps with convex potentials. Comm. Pure Appl. Math.45 (1992) 1141-1151.  
  14. L.A. Caffarelli, Boundary regularity of maps with convex potentials. II. Ann. of Math.144 (1996) 3, 453-496.  
  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.  
  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.  
  21. U. Frischet al., Back to the early Universe by optimal mass transportation. Nature417 (2002) 260-262.  
  22. W. Gangbo and R.J. McCann, The geometry of optimal transportation. Acta Math.177 (1996) 113-161.  
  23. W. Gangbo and R.J. McCann, Shape recognition via Wasserstein distance. Quart. Appl. Math.58 (2000) 705-737.  
  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.  
  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.  
  27. R. Jonker and A. Volgenant, A shortest augmenting path algorithm for dense and sparse linear assignment problem. Computing38 (1987) 325-340.  
  28. R. Jordan, D. Kinderlehrer and F. Otto, The variational formulation of the Fokker-Planck equation. SIAM J. Math. Anal.29 (1998) 1-17.  
  29. T. Kaijser, Computing the Kantorovich distance for images. J. Math. Imaging Vision9 (1998) 173-198.  
  30. L.V. Kantorovich, On the translocation of masses. C. R. (Doklady) Acad. Sci. URSS (N.S.)37 (1942) 199-201.  
  31. D. Kinderlehrer and N. Walkington, Approximation of Parabolic Equations based upon a Wasserstein metric. ESAIM: M2AN33 (1999) 837-852.  
  32. S.A. Kochengin and V.I. Oliker, Determination of reflector surfaces from near-field scattering data. Inverse Problems13 (1997) 363-373.  
  33. R.J. McCann, Polar factorization of maps on Riemannian manifolds. Geom. Funct. Anal.11 (2001) 589-608.  
  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 Equations26 (2001) 101-174.  
  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.  
  38. A. Shnirelman, Generalized fluid flows, their approximation and applications. Geom. Funct. Anal.4 (1994) 586-620.  
  39. C. Villani, Topics in mass transport. Lecture notes (2000).  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.