JournalsjemsVol. 21, No. 9pp. 2603–2651

Convergence of a Newton algorithm for semi-discrete optimal transport

  • Jun Kitagawa

    Michigan State University, East Lansing, USA

  • Quentin Mérigot

    Université Paris-Sud, Orsay, France

  • Boris Thibert

    Université Grenoble Alpes, Grenoble, France
Convergence of a Newton algorithm for semi-discrete optimal transport cover
Download PDF

A subscription is required to access this article.

Abstract

A popular way to solve optimal transport 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 algorithm in this setting, 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.

Cite this article

Jun Kitagawa, Quentin Mérigot, Boris Thibert, Convergence of a Newton algorithm for semi-discrete optimal transport. J. Eur. Math. Soc. 21 (2019), no. 9, pp. 2603–2651

DOI 10.4171/JEMS/889