Colloquium


DATE2019-05-23¡@16:10-17:00

PLACE¼Æ¾ÇÀ]3174±Ð«Ç

SPEAKERJun Kitagawa ±Ð±Â¡]Department of Mathematics, Michigan State University¡^

TITLEConvergence of a Damped Newton Algorithm under Regularity Conditions for Optimal Transport

ABSTRACT The optimal transport (or Monge-Kantorovich) problem is an optimization problem that has surprisingly deep ties to various branches of mathematics. In particular, the semi-discrete problem (where one transports an absolutely continuous measure to a discrete one) is related to computational geometry. I will discuss a damped Newton algorithm for such a semi-discrete problem, along with a rigorous analysis of convergence rates. For costs satisfying standard conditions arising in the PDE regularity theory of optimal transport, we show this algorithm enjoys global linear convergence; this is proved in turn by exploiting Loeper's geometric interpretation of the so-called MTW conditions. This talk is based on joint work with Quentin Mérigot and Boris Thibert.