Thumbnail

Minimal convex extensions and finite difference discretisation of the quadratic Monge–Kantorovich problem

Duval, Vincent; Benamou, Jean-David (2018), Minimal convex extensions and finite difference discretisation of the quadratic Monge–Kantorovich problem, European Journal of Applied Mathematics, p. 1-38. 10.1017/S0956792518000451

View/Open
Type
Article accepté pour publication ou publié
Date
2018
Journal name
European Journal of Applied Mathematics
Publisher
Cambridge University Press
Pages
1-38
Publication identifier
Metadata
Show full item record
Author(s)
Duval, Vincent cc
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Benamou, Jean-David
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Abstract (EN)
We present an adaptation of the Monge–Ampère (MA) lattice basis reduction scheme to the MA equation with second boundary value condition, provided the target is a convex set. This yields a fast adaptive method to numerically solve the optimal transport (OT) problem between two absolutely continuous measures, the second of which has convex support. The proposed numerical method actually captures a specific Brenier solution which is minimal in some sense. We prove the convergence of the method as the grid step size vanishes and show with numerical experiments that it is able to reproduce subtle properties of the OT problem.
Subjects / Keywords
Optimal transport; Monge-Ampère equation; finite-difference scheme