We construct Two-Point Flux Approximation (TPFA) finite volume schemes to solve the quadratic optimal transport problem in its dynamic form, namely the problem originally introduced by Benamou and Brenier. We show numerically that these type of discretizations are prone to form instabilities in their more natural implementation, and we propose a variation based on nested meshes in order to overcome these issues. Despite the lack of strict convexity of the problem, we also derive quantitative estimates on the convergence of the method, at least for the discrete potential and the discrete cost. Finally, we introduce a strategy based on the barrier method to solve the discrete optimization problem.
Keywords: Dynamical optimal transport, finite volumes, barrier method
@article{M2AN_2021__55_5_1847_0,
author = {Natale, Andrea and Todeschi, Gabriele},
title = {Computation of optimal transport with finite volumes},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
pages = {1847--1871},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {5},
doi = {10.1051/m2an/2021041},
mrnumber = {4313377},
zbl = {1477.65177},
language = {en},
url = {https://www.numdam.org/articles/10.1051/m2an/2021041/}
}
TY - JOUR AU - Natale, Andrea AU - Todeschi, Gabriele TI - Computation of optimal transport with finite volumes JO - ESAIM: Mathematical Modelling and Numerical Analysis PY - 2021 SP - 1847 EP - 1871 VL - 55 IS - 5 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/m2an/2021041/ DO - 10.1051/m2an/2021041 LA - en ID - M2AN_2021__55_5_1847_0 ER -
%0 Journal Article %A Natale, Andrea %A Todeschi, Gabriele %T Computation of optimal transport with finite volumes %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2021 %P 1847-1871 %V 55 %N 5 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/m2an/2021041/ %R 10.1051/m2an/2021041 %G en %F M2AN_2021__55_5_1847_0
Natale, Andrea; Todeschi, Gabriele. Computation of optimal transport with finite volumes. ESAIM: Mathematical Modelling and Numerical Analysis , Tome 55 (2021) no. 5, pp. 1847-1871. doi: 10.1051/m2an/2021041
[1] , and , Mean field games: numerical methods for the planning problem. SIAM J. Control Optim. 50 (2012) 77–109. | MR | Zbl | DOI
[2] and , On hopf’s formulas for solutions of Hamilton-Jacobi equations. Nonlinear Anal.: Theory Methods App. 8 (1984) 1373–1381. | MR | Zbl | DOI
[3] and , A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem. Numer. Math. 84 (2000) 375–393. | MR | Zbl | DOI
[4] and , Augmented lagrangian methods for transport optimization, mean field games and degenerate elliptic equations. J. Optim. Theory App. 167 (2015) 1–26. | MR | Zbl | DOI
[5] , and , An augmented lagrangian approach to wasserstein gradient flows and applications. ESAIM: Proce. Surv. 54 (2016) 1–17. | MR | Zbl | DOI
[6] , and , Numerical solution of saddle point problems. Acta Numer. 14 (2005) 1–137. | MR | Zbl | DOI
[7] and , Convex Optimization. Cambridge University Press (2004). | MR | Zbl | DOI
[8] , and , A variational finite volume scheme for wasserstein gradient flows. Numer. Math. 146 (2020) 437–480. | MR | Zbl | DOI
[9] , , and , Primal dual methods for wasserstein gradient flows. Found. Comput. Math. (2021). DOI: . | DOI | MR | Zbl
[10] , and , Finite volume scheme for multi-dimensional drift-diffusion equations and convergence analysis. Math. Modell. Numer. Anal. 37 (2003) 319–338. | MR | Zbl | Numdam | DOI
[11] , , and , Computation of optimal transport on discrete metric measure spaces. Numer. Math. 144 (2020) 157–200. | MR | Zbl | DOI
[12] and , -convergence and numerical schemes for elliptic problems. SIAM J. Numer. Anal. 41 (2003) 539–562. | MR | Zbl | DOI
[13] , and , Finite volume methods. In: Vol. 7 of Handbook of Numerical Analysis (2000) 713–1020. | MR | Zbl
[14] , and , Discretization of heterogeneous and anisotropic diffusion problems on general nonconforming meshes sushi: a scheme using stabilization and hybrid interfaces. IMA J. Numer. Anal. 30 (2009) 1009–1043. | MR | Zbl | DOI
[15] , and , Towards a stationary Monge-Kantorovich dynamics: the physarum polycephalum experience. SIAM J. Appl. Math. 78 (2018) 651–676. | MR | Zbl | DOI
[16] , , and , Numerical solution of Monge-Kantorovich equations via a dynamic formulation. J. Sci. Comput. 82 (2020) 1–26. | MR | Zbl | DOI
[17] , and , Interior methods for nonlinear optimization. SIAM Rev. 44 (2002) 525–597. | MR | Zbl | DOI
[18] FVCAV, Benchmark. https://www.i2m.univ-amu.fr/fvca5/benchmark/Meshes/index.html.
[19] , and , Scaling limits of discrete optimal transport. Preprint (2018). | arXiv | MR | Zbl
[20] , Interior point methods 25 years later. Eur. J. Oper. Res. 218 (2012) 587–601. | MR | Zbl | DOI
[21] , Unconditional convergence for discretizations of dynamical optimal transport. Preprint (2019). | arXiv | MR | Zbl
[22] , , and , Dynamical optimal transport on discrete surfaces. ACM Trans. Graphics (TOG) 37 (2018) 1–16. | DOI
[23] , and , Computations of optimal transport distance with fisher information regularization. J. Sci. Comput. 75 (2018) 1581–1595. | MR | Zbl | DOI
[24] and , A mixed finite element discretization of dynamical optimal transport. Working paper or Preprint (2020). | arXiv
[25] and , TPFA finite volume approximation of Wasserstein gradient flows. In: Finite Volumes for Complex Applications IX – Methods, Theoretical Aspects, Examples. Springer International Publishing (2020) 193–201. | MR | Zbl | DOI
[26] , and , Optimal transport with proximal splitting. SIAM J. Imaging Sci. 7 (2014) 212–238. | MR | Zbl | DOI
[27] and , Interior point methods for nonlinear optimization, edited by and . In: Nonlinear Optimization. Vol. 1989 of Lecture Notes in Mathematics. Springer Berlin Heidelberg (2010). | MR | Zbl | DOI
[28] , Optimal Transport for Applied Mathematicians. Birkäuser, NY (2015) 99–102. | MR
[29] and , Convexity of the support of the displacement interpolation: counter examples. Appl. Math. Lett. 58 (2016) 152–158. | MR | Zbl | DOI
Cité par Sources :
