论文标题
通过内点方法解决动力学最佳传输的有效预处理
Efficient preconditioners for solving dynamical optimal transport via interior point methods
论文作者
论文摘要
在本文中，我们以动态形式（所谓的Benamou-Brenier公式）解决了二次最佳传输问题的数值解决方案。当使用内点方法求解时，主要计算瓶颈是由相关的牛顿 - 拉夫森方案引起的大鞍点线性系统的解决方案。本文的主要目的是设计有效的预处理，以通过迭代方法求解这些线性系统。在拟议的预处理中，我们基于构成这些鞍点线性系统的双重Schur补充的操作员的部分换向介绍，我们将其称为$ \ boldsymbol {b} \ boldsymbol {b} $ - 预定器。一系列数值测试表明，尽管在内部点方法的最后一步中表现恶化，但$ \ boldsymbol {b} \ boldsymbol {b} $ - 预先调节器还是提出的最有效的。实际上，相对于用于离散问题的未知数数量，唯一具有CPU时间比线性较差的CPU时间的人。
In this paper we address the numerical solution of the quadratic optimal transport problem in its dynamical form, the so-called Benamou-Brenier formulation. When solved using interior point methods, the main computational bottleneck is the solution of large saddle point linear systems arising from the associated Newton-Raphson scheme. The main purpose of this paper is to design efficient preconditioners to solve these linear systems via iterative methods. Among the proposed preconditioners, we introduce one based on the partial commutation of the operators that compose the dual Schur complement of these saddle point linear systems, which we refer as $\boldsymbol{B}\boldsymbol{B}$-preconditioner. A series of numerical tests show that the $\boldsymbol{B}\boldsymbol{B}$-preconditioner is the most efficient among those presented, despite a performance deterioration in the last steps of the interior point method. It is in fact the only one having a CPU-time that scales only slightly worse than linearly with respect to the number of unknowns used to discretize the problem.
