Numerical Methods for the Optimal Transport Problem
The problem of optimal transportation, which involves finding the most
cost-efficient mapping between two measures, arises in many different applications. However, the numerical solution of this problem remains extremely challenging and standard techniques can fail to compute the correct solution. Recently, several methods have been proposed that obtain the solution by solving the Monge-Ampere equation, a fully nonlinear elliptic partial differential equation (PDE), coupled to a non-standard implicit boundary condition. Unfortunately, standard techniques for analyzing numerical methods for fully nonlinear elliptic equations fail in this setting. We introduce a modified PDE that couples
the usual Monge-Ampere equation to a Hamilton-Jacobi equation that restricts the transportation of mass. This leads to a simple framework for guaranteeing that a numerical method will converge to the true solution, which applies to a large class of approximation schemes. We describe some simple examples. A range of challenging computational examples demonstrate the effectiveness of this method, including the recent application of these methods to problems in beam shaping and seismic inversion.