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 metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01290496
Contributor : Quentin Mérigot <>
Submitted on : Friday, March 18, 2016 - 11:50:39 AM
Last modification on : Wednesday, August 7, 2019 - 2:32:05 PM
Long-term archiving on: Monday, June 20, 2016 - 1:31:17 AM

File

ma.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

815

Files downloads

292