论文标题
最佳运输：离散和算法
Optimal transport: discretization and algorithms
论文作者
论文摘要
本章介绍了最佳运输问题的数值解决方案的技术。我们将考虑这些问题的几个离散化，我们将重点关注对解决离散问题的算法的数学分析。我们将详细描述以下离散化和相应的算法：分配问题和Bertsekas拍卖算法；熵正则化和sndhorn-knopp的算法；半混凝土的最佳运输和Oliker-Prussner或抑制了牛顿的算法，最后是半混凝土熵正规化。我们的演讲强调了这些算法与它们与坎托罗维奇二元性理论的联系之间的相似性。
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.
