Weak Monge-Ampère solutions of the semi-discrete optimal transportation problem

Jean David Benamou, Brittany D. Froese

Research output: Chapter in Book/Report/Conference proceedingChapter

1 Scopus citations

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 languageEnglish (US)
Title of host publicationTopological Optimization and Optimal Transport
Subtitle of host publicationIn the Applied Sciences
Publisherde Gruyter
Pages175-203
Number of pages29
ISBN (Electronic)9783110430417
ISBN (Print)9783110439267
StatePublished - 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

Fingerprint

Dive into the research topics of 'Weak Monge-Ampère solutions of the semi-discrete optimal transportation problem'. Together they form a unique fingerprint.

Cite this