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

JOURNAL OF COMPUTATIONAL PHYSICS

卷:260

Article

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

[1] INRIA, F-78153 Rocquencourt, France

[2] Simon Fraser Univ, Dept Math, Burnaby, BC V5A 1S6, Canada

关键词: Optimal Transportation;    Monge Ampere equation;    Numerical methods;    Finite difference methods;    Viscosity solutions;    Monotone schemes;    Convexity;    Fully nonlinear elliptic partial differential equations;   

DOI  :  10.1016/j.jcp.2013.12.015

来源: Elsevier

【 摘 要 】

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 [4]. Solutions are computed with densities supported on non-convex and disconnected domains. Computational examples demonstrate robust performance on singular solutions and fast computational times. (C) 2013 Elsevier Inc. All rights reserved.

【 授权许可】

Free