Abstract
We consider the Monge-Kantorovich optimal transportation (OT) problem between two measures, one of which is a weighted sum of Diracs. This problem is traditionally solved using geometric methods based on the computation of Laguerre cells. We review the duality between Brenier/Pogorelov weak solutions and the classical Aleksandrov measure formulation. It is well known that the OT problem can be reformulated as a Monge-Ampère elliptic partial differential equation. However, existing numerical methods for this non-linear PDE require the measures to have finite density. We propose a new formulation that couples the viscosity and Aleksandrov solution definitions and show that it is equivalent to the original problem. Moreover, we describe a local reformulation of the subgradient measure at the Diracs, which makes use of one-sided directional derivatives. This leads to a consistent, monotone discretization of the equation. Computational results demonstrate the correctness of this scheme when methods designed for conventional viscosity solutions fail.
Original language | English (US) |
---|---|
Title of host publication | Topological Optimization and Optimal Transport |
Subtitle of host publication | In the Applied Sciences |
Publisher | de Gruyter |
Pages | 175-203 |
Number of pages | 29 |
ISBN (Electronic) | 9783110430417 |
ISBN (Print) | 9783110439267 |
DOIs | |
State | Published - Aug 7 2017 |
All Science Journal Classification (ASJC) codes
- General Mathematics
- General Computer Science
- General Engineering
Keywords
- Aleksandrov solutions
- Finite difference methods
- Monge-Ampère equation
- Optimal transportation
- Viscosity solutions