Optimal transport via a Monge-Ampère optimization problem
This work provides a novel theoretical framework and convergence guarantee for computing optimal transport maps, which is important for researchers in optimization and machine learning who need accurate OT solutions.
The authors reformulate the optimal transport problem with quadratic cost as a convex infinite-dimensional optimization problem via the Monge-Ampère equation, propose a finite-dimensional discretization that yields piecewise affine convex functions, and prove convergence to the continuous solution under regularity conditions. Numerical experiments demonstrate the method's practicality.
We rephrase Monge's optimal transportation (OT) problem with quadratic cost--via a Monge-Ampère equation--as an infinite-dimensional optimization problem, which is in fact a convex problem when the target is a log-concave measure with convex support. We define a natural finite-dimensional discretization to the problem and associate a piecewise affine convex function to the solution of this discrete problem. The discrete problems always admit a solution, which can be obtained by standard convex optimization algorithms whenever the target is a log-concave measure with convex support. We show that under suitable regularity conditions the convex functions retrieved from the discrete problems converge to the convex solution of the original OT problem furnished by Brenier's theorem. Also, we put forward an interpretation of our convergence result that suggests applicability to the convergence of a wider range of numerical methods for OT. Finally, we demonstrate the practicality of our convergence result by providing visualizations of OT maps as well as of the dynamic OT problem obtained by solving the discrete problem numerically.