HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Convergence of a Newton algorithm for semi-discrete optimal transport

Abstract : Many problems in geometric optics or convex geometry can be recast as optimal transport problems and a popular way to solve these problems numerically is to assume that the source probability measure is absolutely continuous while the target measure is finitely supported. We introduce a damped Newton's algorithm for this type of problems, which is experimentally efficient, and we establish its global linear convergence for cost functions satisfying an assumption that appears in the regularity theory for optimal transport.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download

Contributor : Quentin Mérigot Connect in order to contact the contributor
Submitted on : Friday, March 18, 2016 - 11:50:39 AM
Last modification on : Friday, February 4, 2022 - 3:14:09 AM
Long-term archiving on: : Monday, June 20, 2016 - 1:31:17 AM


Files produced by the author(s)


  • HAL Id : hal-01290496, version 1
  • ARXIV : 1603.05579


Jun Kitagawa, Quentin Mérigot, Boris Thibert. Convergence of a Newton algorithm for semi-discrete optimal transport. 2016. ⟨hal-01290496⟩



Record views


Files downloads