Numerical solution of the Monge–Kantorovich problem by density lift-up continuation
ESAIM: Mathematical Modelling and Numerical Analysis , Tome 49 (2015) no. 6, pp. 1577-1592.

We present an numerical method to solve the L 2 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.

Reçu le :
DOI : 10.1051/m2an/2015024
Classification : 68U01, 65K05
Mots clés : Optimal transport, Monge–Kantorovich problem, numerical solution, Newton method, continuation approach
Bouharguane, Afaf 1 ; Iollo, Angelo 1 ; Weynans, Lisl 1

1 Institut de Mathématiques de Bordeaux, UMR 5251 CNRS, Université de Bordeaux and Equipe-projet MEMPHIS, Inria Bordeaux Sud-Ouest, 33405 Talence, France.
@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://archive.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://archive.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://archive.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 , Tome 49 (2015) no. 6, pp. 1577-1592. doi : 10.1051/m2an/2015024. http://archive.numdam.org/articles/10.1051/m2an/2015024/

S. Angenent, S. Haker and A. Tennenbaum, Minimizing flows for the Monge–Kantorovich problem. SIAM J. Math. Anal. 35 (2003) 61–97. | DOI | MR | Zbl

J.-D. Benamou and Y. Brenier, 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).

Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 64 (1991) 375–417. | DOI | MR | Zbl

E.J. Dean and R. Glowinski, Numerical methods for fully nonlinear elliptic equations of the mongeampre type. Comput. Methods Appl. Mech. Eng. 195 (2006) 1344–1386. | DOI | MR | Zbl

A. Iollo and D. Lombardi, A Lagrangian scheme for the solution of the optimal mass transfer problem. J. Comput. Phys. 230 (2011) 3430–3442. | DOI | MR | Zbl

G. Loeper and Francesca Rapetti, 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).

N. Papadakis, G. Peyré and E. Oudet, 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

L. Weynans and A. Magni, Consistency, accuracy and entropy behaviour of remeshed particle methods. ESAIM: M2AN 47 (2013) 57–81. | DOI | Numdam | MR | Zbl

Cité par Sources :