Optimal transport: discretization and algorithms

DOI10.1016/BS.HNA.2020.10.001arXiv2003.00855MaRDI QIDQ6335963

Publication date: 2 March 2020

Abstract: This chapter describes techniques for the numerical resolution of optimal transport problems. We will consider several discretizations of these problems, and we will put a strong focus on the mathematical analysis of the algorithms to solve the discretized problems. We will describe in detail the following discretizations and corresponding algorithms: the assignment problem and Bertsekas auction's algorithm; the entropic regularization and Sinkhorn-Knopp's algorithm; semi-discrete optimal transport and Oliker-Prussner or damped Newton's algorithm, and finally semi-discrete entropic regularization. Our presentation highlights the similarity between these algorithms and their connection with the theory of Kantorovich duality.

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Optimal transportation (49Q22)

This page was built for publication: Optimal transport: discretization and algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6335963)