We present a method to efficiently compute Wasserstein gradient flows. Our approach is based on a generalization of the back-and-forth method (BFM) introduced in Jacobs and Léger [Numer. Math. 146 (2020) 513–544.]. to solve optimal transport problems. We evolve the gradient flow by solving the dual problem to the JKO scheme. In general, the dual problem is much better behaved than the primal problem. This allows us to efficiently run large scale gradient flows simulations for a large class of internal energies including singular and non-convex energies.
Keywords: Optimal transport, Wasserstein gradient flows, JKO scheme, back-and-forth method, Porous media equation, Crowd motion models, Numerical optimization
@article{COCV_2021__27_1_A30_0,
author = {Jacobs, Matt and Lee, Wonjun and L\'eger, Flavien},
title = {The back-and-forth method for {Wasserstein} gradient flows},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
year = {2021},
publisher = {EDP-Sciences},
volume = {27},
doi = {10.1051/cocv/2021029},
language = {en},
url = {https://www.numdam.org/articles/10.1051/cocv/2021029/}
}
TY - JOUR AU - Jacobs, Matt AU - Lee, Wonjun AU - Léger, Flavien TI - The back-and-forth method for Wasserstein gradient flows JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2021 VL - 27 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/cocv/2021029/ DO - 10.1051/cocv/2021029 LA - en ID - COCV_2021__27_1_A30_0 ER -
%0 Journal Article %A Jacobs, Matt %A Lee, Wonjun %A Léger, Flavien %T The back-and-forth method for Wasserstein gradient flows %J ESAIM: Control, Optimisation and Calculus of Variations %D 2021 %V 27 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/cocv/2021029/ %R 10.1051/cocv/2021029 %G en %F COCV_2021__27_1_A30_0
Jacobs, Matt; Lee, Wonjun; Léger, Flavien. The back-and-forth method for Wasserstein gradient flows. ESAIM: Control, Optimisation and Calculus of Variations, Tome 27 (2021), article no. 28. doi: 10.1051/cocv/2021029
[1] , and , Quasi-static evolution and congested crowd transport. Nonlinearity 27 (2014) 823–858.
[2] , and , An augmented Lagrangian approach to Wasserstein gradient flows and applications. ESAIM: PROC. 54 (2016) 1–17.
[3] , , and , Discretization of functionals involving the Monge–Ampère operator. Numer. Math. 134 (2016) 611–636.
[4] , and , A mixed finite element method for nonlinear diffusion equations. Kinet. Relat. Models 3 (2010) 59–83.
[5] , Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 44 (1991) 375–417.
[6] , , and , Primal dual methods for Wasserstein gradient flows. Preprint (2019). | arXiv
[7] , , and , Convergence of entropic schemes for optimal transport and gradient flows. SIAM J. Math. Anal. 49 (2017) 1385–1418.
[8] and , Numerical simulation of diffusive and aggregation phenomena in nonlinear continuity equations by evolving diffeomorphisms. SIAM J. Sci. Comput. 31 (2009/10) 4305–4329.
[9] , , and , Variational asymptotic preserving scheme for the Vlasov–Poisson–Fokker–Planck system. Preprint (2020). | arXiv
[10] , , and , BV estimates in optimal transportation and applications. Arch. Ration. Mech. Anal. 219 (2016) 829–860.
[11] , Partial differential equations. Vol. 19 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, second edition (2010) 829–860.
[12] , Unconditionally gradient stable time marching the Cahn–Hilliard equation. MRS Proc. 529 (1998) 39.
[13] , An elementary proof of the polar factorization of vector-valued functions. Arch. Ratl. Mech. Anal. 128 (1994) 381–399.
[14] , Quelques problemes d’analyse non convexe. Habilitation à diriger des recherches en mathématiques. Université de Metz (1995).
[15] , Quelques problèmes d’analyse non convexe. Habilitation à diriger des recherches en mathématiques. Habilitation, Université de Metz (January 1995).
[16] and , The geometry of optimal transportation. Acta Math. 177 (1996) 113–161.
[17] Scaling, self-similarity, and intermediate asymptotics. With a foreword by . Vol. 14 of Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge (1996).
[18] , Scaling. Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge (2003). With a foreword by Alexandre Chorin.
[19] , and , The variational formulation of the Fokker–Planck equation. SIAM J. Math. Anal. 29 (1998) 1–17.
[20] , and , The L1-contraction principle in optimal transport. Preprint (2020). | arXiv
[21] and , A fast approach to optimal transport: the back-and-forth method. Numer. Math. 146 (2020) 513–544.
[22] , , and , Lagrangian discretization of crowd motion and linear diffusion. SIAM J. Numer. Anal. 58 (2020) 2093–2118.
[23] , Faster than the fast Legendre transform, the linear-time Legendre transform. Numer. Algor. 16 (1997) 171–185.
[24] , Vol. 87 of Introductory lectures on convex optimization: A basic course. Springer Science & Business Media (2013).
[25] , The geometry of dissipative evolution equations: the porous medium equation. Commun. Partial Differ. Equ. 26 (2001) 101–174.
[26] , Entropic approximation of Wasserstein gradient flows. SIAM J. Imag. Sci. 8 (2015) 2323–2351.
[27] , Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling. Vol. 87 of Progress in Nonlinear Differential Equations and their Applications. Birkhäuser/Springer, Cham (2015).
[28] , The porous medium equation: mathematical theory. Oxford University Press (2007).
Cité par Sources :
