We present an numerical method to solve the Monge–Kantorovich problem. The method is based on a continuation approach where we iteratively solve the linearized mass conservation equation, progressively decreasing a constant lift-up to map compact support densities in the limit. A Lagrangian as well as an Eulerian integration scheme are proposed. Several examples relative to the transport of two-dimensional densities are investigated, showing that the present methods can significantly reduce the computational effort.
DOI : 10.1051/m2an/2015024
Mots-clés : Optimal transport, Monge–Kantorovich problem, numerical solution, Newton method, continuation approach
@article{M2AN_2015__49_6_1577_0,
author = {Bouharguane, Afaf and Iollo, Angelo and Weynans, Lisl},
title = {Numerical solution of the {Monge{\textendash}Kantorovich} problem by density lift-up continuation},
journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
pages = {1577--1592},
publisher = {EDP-Sciences},
volume = {49},
number = {6},
year = {2015},
doi = {10.1051/m2an/2015024},
mrnumber = {3423265},
zbl = {1348.65098},
language = {en},
url = {http://www.numdam.org/articles/10.1051/m2an/2015024/}
}
TY - JOUR AU - Bouharguane, Afaf AU - Iollo, Angelo AU - Weynans, Lisl TI - Numerical solution of the Monge–Kantorovich problem by density lift-up continuation JO - ESAIM: Mathematical Modelling and Numerical Analysis PY - 2015 SP - 1577 EP - 1592 VL - 49 IS - 6 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/m2an/2015024/ DO - 10.1051/m2an/2015024 LA - en ID - M2AN_2015__49_6_1577_0 ER -
%0 Journal Article %A Bouharguane, Afaf %A Iollo, Angelo %A Weynans, Lisl %T Numerical solution of the Monge–Kantorovich problem by density lift-up continuation %J ESAIM: Mathematical Modelling and Numerical Analysis %D 2015 %P 1577-1592 %V 49 %N 6 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/m2an/2015024/ %R 10.1051/m2an/2015024 %G en %F M2AN_2015__49_6_1577_0
Bouharguane, Afaf; Iollo, Angelo; Weynans, Lisl. Numerical solution of the Monge–Kantorovich problem by density lift-up continuation. ESAIM: Mathematical Modelling and Numerical Analysis , Optimal Transport, Tome 49 (2015) no. 6, pp. 1577-1592. doi : 10.1051/m2an/2015024. http://www.numdam.org/articles/10.1051/m2an/2015024/
, and , Minimizing flows for the Monge–Kantorovich problem. SIAM J. Math. Anal. 35 (2003) 61–97. | DOI | MR | Zbl
and , A computational fluid mechanics solution to the Monge–Kantorovich mass transfer problem. Numer. Mat. 84 (2000) 375–393. | DOI | MR | Zbl
J.-D. Benamou, A. Oberman and B. Froese, Numerical solution of the second boundary value problem for the Elliptic Monge-Ampère equation. Rapport de recherche (2012).
, Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 64 (1991) 375–417. | DOI | MR | Zbl
and , Numerical methods for fully nonlinear elliptic equations of the mongeampre type. Comput. Methods Appl. Mech. Eng. 195 (2006) 1344–1386. | DOI | MR | Zbl
and , A Lagrangian scheme for the solution of the optimal mass transfer problem. J. Comput. Phys. 230 (2011) 3430–3442. | DOI | MR | Zbl
and , Numerical solution of the Monge-Ampere equation by a newton’s algorithm. C. R. Acad. Sci. Paris, Ser. I 340 (2005) 319–324. | DOI | MR | Zbl
G. Monge, Memoire sur la théorie des déblais et des remblais. Histoire de l’Académie des Sciences de Paris (1781).
, and , Optimal transport with proximal splitting. SIAM J. Imaging Sci. 7 (2014) 212–238. | DOI | MR | Zbl
L.-P. Saumier, M. Agueh and B. Khouider. An efficient numerical algorithm for the l2 optimal transport problem with periodic densities. IMA J. Appl. Math. (2013). | MR
C. Villani, Topics in Optimal Transportation. American Mathematical Society, 1st edition (2003). | MR | Zbl
C. Villani, Optimal Transport, old and new. Springer-Verlag, 1st edition (2009). | MR | Zbl
and , Consistency, accuracy and entropy behaviour of remeshed particle methods. ESAIM: M2AN 47 (2013) 57–81. | DOI | Numdam | MR | Zbl
Cité par Sources :
