Thumbnail

Convergence of a Newton algorithm for semi-discrete optimal transport

Kitagawa, Jun; Mérigot, Quentin; Thibert, Boris (2016), Convergence of a Newton algorithm for semi-discrete optimal transport. https://basepub.dauphine.fr/handle/123456789/17408

View/Open
Type
Document de travail / Working paper
Date
2016
Series title
Cahier de recherche CEREMADE, Université Paris-Dauphine
Pages
42
Metadata
Show full item record
Author(s)
Kitagawa, Jun

Mérigot, Quentin
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Thibert, Boris
Laboratoire Jean Kuntzmann [LJK]
Abstract (EN)
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.
Subjects / Keywords
optimal transport; Monge-Ampère equation; Laguerre diagram