Unconditional convergence for discretizations of dynamical optimal transport

Lavenant, Hugo

doi:10.1090/mcom/3567

Unconditional convergence for discretizations of dynamical optimal transport
HTML articles powered by AMS MathViewer

by Hugo Lavenant HTML | PDF

Math. Comp. 90 (2021), 739-786 Request permission

Abstract:

The dynamical formulation of optimal transport, also known as Benamou–Brenier formulation or computational fluid dynamics formulation, amounts to writing the optimal transport problem as the optimization of a convex functional under a PDE constraint, and can handle a priori a vast class of cost functions and geometries. Several discretizations of this problem have been proposed, leading to computations on flat spaces as well as Riemannian manifolds, with extensions to mean field games and gradient flows in the Wasserstein space.

In this paper, we provide a framework which guarantees convergence under mesh refinement of the solutions of the space-time discretized problems to the one of the infinite-dimensional problem for quadratic optimal transport. The convergence holds without condition on the ratio between spatial and temporal step sizes, and can handle arbitrary positive measures as input, while the underlying space can be a Riemannian manifold. Both the finite volume discretization proposed by Gladbach, Kopfer, and Maas, as well as the discretization over triangulations of surfaces studied by the present author in collaboration with Claici, Chien, and Solomon, fit in this framework.

References

Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré, Gradient flows in metric spaces and in the space of probability measures, 2nd ed., Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel, 2008. MR 2401600
Rossella Bartolo, Anna Germinario, and Miguel Sánchez, Convexity of domains of Riemannian manifolds, Ann. Global Anal. Geom. 21 (2002), no. 1, 63–83. MR 1889250, DOI 10.1023/A:1014231603588
Jean-David Benamou and Yann Brenier, A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem, Numer. Math. 84 (2000), no. 3, 375–393. MR 1738163, DOI 10.1007/s002110050002
Jean-David Benamou and Guillaume Carlier, Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations, J. Optim. Theory Appl. 167 (2015), no. 1, 1–26. MR 3395203, DOI 10.1007/s10957-015-0725-9
Jean-David Benamou, Guillaume Carlier, and Maxime Laborde, An augmented Lagrangian approach to Wasserstein gradient flows and applications, Gradient flows: from theory to application, ESAIM Proc. Surveys, vol. 54, EDP Sci., Les Ulis, 2016, pp. 1–17 (English, with English and French summaries). MR 3565819, DOI 10.1051/proc/201654001
Jean-David Benamou, Guillaume Carlier, and Filippo Santambrogio, Variational mean field games, Active particles. Vol. 1. Advances in theory, models, and applications, Model. Simul. Sci. Eng. Technol., Birkhäuser/Springer, Cham, 2017, pp. 141–171. MR 3644590
Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, 3rd ed., Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. MR 2373954, DOI 10.1007/978-0-387-75934-0
G. Buttazzo, C. Jimenez, and E. Oudet, An optimization problem for mass transportation with congested dynamics, SIAM J. Control Optim. 48 (2009), no. 3, 1961–1976. MR 2516195, DOI 10.1137/07070543X
J. A. Carrillo, K. Craig, L. Wang, and C. Wei, Primal dual methods for wasserstein gradient flows, arXiv preprint arXiv:1901.08081, (2019).
Lénaïc Chizat, Gabriel Peyré, Bernhard Schmitzer, and François-Xavier Vialard, An interpolating distance between optimal transport and Fisher-Rao metrics, Found. Comput. Math. 18 (2018), no. 1, 1–44. MR 3749413, DOI 10.1007/s10208-016-9331-y
Matthias Erbar, The heat equation on manifolds as a gradient flow in the Wasserstein space, Ann. Inst. Henri Poincaré Probab. Stat. 46 (2010), no. 1, 1–23 (English, with English and French summaries). MR 2641767, DOI 10.1214/08-AIHP306
Matthias Erbar, Martin Rumpf, Bernhard Schmitzer, and Stefan Simon, Computation of optimal transport on discrete metric measure spaces, Numer. Math. 144 (2020), no. 1, 157–200. MR 4050090, DOI 10.1007/s00211-019-01077-z
Nicola Gigli and Jan Maas, Gromov-Hausdorff convergence of discrete transportation metrics, SIAM J. Math. Anal. 45 (2013), no. 2, 879–899. MR 3045651, DOI 10.1137/120886315
Peter Gladbach, Eva Kopfer, and Jan Maas, Scaling limits of discrete optimal transport, SIAM J. Math. Anal. 52 (2020), no. 3, 2759–2802. MR 4110822, DOI 10.1137/19M1243440
K. Guittet, On the time-continuous mass transport problem and its approximation by augmented Lagrangian techniques, SIAM J. Numer. Anal. 41 (2003), no. 1, 382–399. MR 1974507, DOI 10.1137/S0036142901386069
M. Henry, E. Maitre, and V. Perrier, Primal-dual formulation of the dynamic optimal transport using Helmholtz-Hodge decomposition (2019).
Klaus Hildebrandt, Konrad Polthier, and Max Wardetzky, On the convergence of metric and geometric properties of polyhedral surfaces, Geom. Dedicata 123 (2006), 89–112. MR 2299728, DOI 10.1007/s10711-006-9109-5
R. Hug, Analyse mathématique et convergence d’un algorithme pour le transport optimal dynamique: cas des plans de transports non réguliers, ou soumis à des contraintes, PhD thesis, (2016).
Richard Jordan, David Kinderlehrer, and Felix Otto, The variational formulation of the Fokker-Planck equation, SIAM J. Math. Anal. 29 (1998), no. 1, 1–17. MR 1617171, DOI 10.1137/S0036141096303359
H. Lavenant, S. Claici, E. Chien, and J. Solomon, Dynamical optimal transport on discrete surfaces, ACM Transactions on Graphics, 37 (2018), no. 6.
Jan Maas, Gradient flows of the entropy for finite Markov chains, J. Funct. Anal. 261 (2011), no. 8, 2250–2292. MR 2824578, DOI 10.1016/j.jfa.2011.06.009
Robert J. McCann, A convexity principle for interacting gases, Adv. Math. 128 (1997), no. 1, 153–179. MR 1451422, DOI 10.1006/aima.1997.1634
Robert J. McCann, Polar factorization of maps on Riemannian manifolds, Geom. Funct. Anal. 11 (2001), no. 3, 589–608. MR 1844080, DOI 10.1007/PL00001679
A. Natale and G. Todeschi A mixed finite element discretization of dynamical optimal transport, arXiv preprint arXiv:2003.04558. (2020).
Felix Otto and Michael Westdickenberg, Eulerian calculus for the contraction in the Wasserstein distance, SIAM J. Math. Anal. 37 (2005), no. 4, 1227–1255. MR 2192294, DOI 10.1137/050622420
Nicolas Papadakis, Gabriel Peyré, and Edouard Oudet, Optimal transport with proximal splitting, SIAM J. Imaging Sci. 7 (2014), no. 1, 212–238. MR 3158785, DOI 10.1137/130920058
S. Pigola and G. Veronelli, The smooth Riemannian extension problem: completeness, arXiv preprint arXiv:1601.05075 (2016).
R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683
Filippo Santambrogio, Optimal transport for applied mathematicians, Progress in Nonlinear Differential Equations and their Applications, vol. 87, Birkhäuser/Springer, Cham, 2015. Calculus of variations, PDEs, and modeling. MR 3409718, DOI 10.1007/978-3-319-20828-2
Cédric Villani, Topics in optimal transportation, Graduate Studies in Mathematics, vol. 58, American Mathematical Society, Providence, RI, 2003. MR 1964483, DOI 10.1090/gsm/058
Cédric Villani, Optimal transport, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 338, Springer-Verlag, Berlin, 2009. Old and new. MR 2459454, DOI 10.1007/978-3-540-71050-9
Feng-Yu Wang, Second fundamental form and gradient of Neumann semigroups, J. Funct. Anal. 256 (2009), no. 10, 3461–3469. MR 2504531, DOI 10.1016/j.jfa.2008.12.010
Feng-Yu Wang, Equivalent semigroup properties for the curvature-dimension condition, Bull. Sci. Math. 135 (2011), no. 6-7, 803–815. MR 2838102, DOI 10.1016/j.bulsci.2011.07.005