Numerical solution of the Optimal Transportation problem using the Monge-Ampere equation

Jean-David Benamou, Brittany D. Froese, Adam M. Oberman

Abstract

A numerical method for the solution of the elliptic Monge-Ampere Partial Differential Equation, with boundary conditions corresponding to the Optimal Transportation (OT) problem is presented. A local representation of the OT boundary conditions is combined with a finite difference scheme for the Monge-Ampere equation. Newton's method is implemented leading to a fast solver, comparable to solving the Laplace equation on the same grid several times. Theoretical justification for the method is given by a convergence proof in the companion paper (Benamou et al., 2012). In this paper, the algorithm is modified to a simpler compact stencil implementation and details of the implementation are given. Solutions are computed with densities supported on non-convex and disconnected domains. Computational examples demonstrate robust performance on singular solutions and fast computational times.
BibTeX
@article{benamou2014numerical,
  author = {Jean-David Benamou and Brittany D. Froese and Adam M. Oberman},
  title = {{Numerical solution of the Optimal Transportation problem using the Monge-Ampere equation}},
  journal = {Journal of Computational Physics},
  year = {2014},
  url = {https://openreview.net/forum?id=fXXGTe3jEZq},
}

Loading related content...

Figure