Brittany Froese: Numerical Solution of the Optimal Transportation Problem Using the Monge-Ampere Equation

Despite the importance of optimal transportation in both theoretical and applied mathematics, the computation of solutions remains an extremely challenging problem. We describe a numerical method for the widely-studied case when the cost is quadratic and mass is being mapped onto a convex set. The solution is obtained by solving the Monge-Ampere equation, a fully nonlinear elliptic partial differential equation (PDE), coupled to a non-standard implicit boundary condition. First, we describe a variational formulation of the PDE operator, which enables us to construct a monotone finite difference discretisation. This is used as the foundation of a more accurate, almost-monotone discretisation. Next, we re-express the transport condition as a Hamilton-Jacobi equation on the boundary. We construct an upwind discretisation of this equation that only requires data inside the domain. Using the theory of viscosity solutions, we prove convergence of the resulting method. A range of challenging computational examples demonstrate the effectiveness and efficiency of this method.