{
  "id": "1603.07435",
  "version": "v1",
  "published": "2016-03-24T04:36:55.000Z",
  "updated": "2016-03-24T04:36:55.000Z",
  "title": "Optimal transport via a Monge-Ampère optimization problem",
  "authors": [
    "Michael Lindsey",
    "Yanir A. Rubinstein"
  ],
  "categories": [
    "math.NA",
    "math.AP"
  ],
  "abstract": "We rephrase Monge's optimal transportation (OT) problem with quadratic cost--via a Monge-Amp\\`ere 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-03-24T04:36:55.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "monge-ampère optimization problem",
      "discrete problem",
      "standard convex optimization algorithms",
      "log-concave measure",
      "convex function"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160307435L"
    }
  }
}