Convergence of a Newton algorithm for semi-discrete optimal transport
Kitagawa, Jun ; Mérigot, Quentin ; Thibert, Boris
HAL, hal-01290496 / Harvested from HAL
Text on HAL
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.
Publié le : 2016-03-17
Classification:  optimal transport,  Monge-Ampère equation,  Laguerre diagram,  49M25, 65K10,  [MATH.MATH-NA]Mathematics [math]/Numerical Analysis [math.NA],  [MATH.MATH-AP]Mathematics [math]/Analysis of PDEs [math.AP],  [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] 
@article{hal-01290496,
     author = {Kitagawa, Jun and M\'erigot, Quentin and Thibert, Boris},
     title = {Convergence of a Newton algorithm for semi-discrete optimal transport},
     journal = {HAL},
     volume = {2016},
     number = {0},
     year = {2016},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-01290496}
}

Kitagawa, Jun; Mérigot, Quentin; Thibert, Boris. Convergence of a Newton algorithm for semi-discrete optimal transport. HAL, Tome 2016 (2016) no. 0, . http://gdmltest.u-ga.fr/item/hal-01290496/