“最优传输理论和计算”系列讲座总结

2021年圣诞夜，Omicron在世界各地渐成强弩之末，希望明年烟消云散。由于疫情的原因，2021年所有的教学都在线上进行，笔者从10月下旬至12月中旬，在网上给了最优传输理论和算法的系列讲座。由于人工智能的浪潮，广大青年学生对于AI的理论和算法表现出空前的热情。我们认为深度学习的核心目的是学习流形上的概率分布，因此求取概率分布之间的变换、衡量概率分布之间的距离是深度学习不可或缺的操作，如何在所有概率测度构成的无穷维空间中做变分是深度学习的理论基础。而这些正是最优传输理论研究的核心问题。由此，笔者选择了这个专题进行深入阐述。

最优传输理论历史悠久，博大精深，数百年间无数科学家为此做出过杰出贡献，并且获得过诺贝尔奖和菲尔兹奖。我们的讲座涵盖了Monge、Kantorovich、Brenier、Benamou、Minkowski、Alexandrov、丘成桐先生、McCann、Caffarelli、汪徐家院士、Arnold、Otto、Villani、Figalli等很多数学家的杰出工作，从经典最优传输理论，凸微分几何和流体力学等角度加以讲解。我们也涵盖了最优传输理论的新近发展，包括最优部分传输的Caffarrelli-McCann，Figalli理论，最优传输映射的奇异集合理论。同时由于听众的主体是具有计算机科学、工程技术的青年学子，我们更加强调算法的设计和实现。在讲解主要理论框架的基础上，详细解释了各种算法的设计原理和实现难点，特别是讲解了很多独到的算法，包括笔者团队基于丘成桐先生几何变分原则设计的球面最优传输算法，最差传输算法以及基于快速Fourier变换的最优传输算法。并且留了大量的编程作业，帮助大家切实掌握计算方法。

这一系列讲座吸引了很多年轻学子，历次讲座都有上千人在线听讲，非常令笔者感动。听众们来自很多领域，有AI领域，医学图像领域，计算机视觉领域，计算机图形学领域，智能制造领域，光学设计领域，更有来自基础数学和计算数学领域的学者们。也有数学领域的博士生，通过这次系列讲座，获得了灵感和启发，完成了博士论文中核心定理的证明，非常令人欣慰！笔者希望这些理论和算法能够被广大听众们应用于各自的领域，使得现代几何更加深入广泛地应用于现代科技。

下面，笔者将这16个讲座的主要内容加以梳理，提纲挈领地帮助大家整理知识图谱，内化到自身的知识结构之中。由于笔者的学识有限，希望大家多多批评指正。

最优传输理论研究如何最经济地将一个概率测度变换到另外一个概率测度，它天然地与凸微分几何和流体力学相联系。在凸微分几何中，凸曲面上有两个测度，一个是曲面的面积，另外一个是曲面的高斯曲率，奇妙之处在于凸曲面本身的几何由这两个测度之间的最优传输映射所决定。而流体运动自然将流体粒子运输，将初始密度变成最终密度。因此我们的讲座主要从三个侧面来阐释最优传输理论：经典的最优传输理论、凸微分几何与流体力学。

如果可导，保测度条件等价于Jacobi方程：

给定传输单位质量的代价函数，Monge问题是在所有保测度映射中寻找总传输代价最小者：

最优传输映射将产地的产品全部运输到销地，如果销地不唯一，则传输映射被推广为传输方案。Kantorovich将传输方案表示成定义在上的联合概率分布，其边际分布为和，， 为任意Borel集合，

等价的，我们定义投影映射和，边际分布的限制可以表示为和. Kantorovich问题表述为：

如果将边际分布限制表达为广义Lagrange乘子，我们得到Kantorovich对偶问题：

我们引入c-变换的概念:

这样，Kantorovich对偶问题改进为：

最优传输方案的支集满足

最优传输方案的支集具有循环单调性，对于支集内的任意个点，对于任意的排列，我们都有：

由循环单调性，我们可以证明最优传输方案等价于最优传输映射。

考察c-变换, 我们得到

如果对于任意固定的，存在唯一的满足上面的方程，则我们说传输代价满足扭曲条件，这时最优传输方案（相关性）变成最优传输映射（因果性）。如果，这里是强凸函数，那么我们有

如果，我们有

代入Jacobi方程，我们得到Brenier问题：求一个凸函数，满足Monge-Ampere方程：

在c-变换中，如果我们固定，那么是一张支撑曲面，（代价决定支撑）；，支撑曲面的包络给出了势能函数，(支撑包络势能)；定义广义微分

最优传输映射 ，（势能微分映射）；最优传输映射的逆映射也是最优传输映射，并且由的广义微分给出，是逆映射的势能, 势能函数都是凸函数（映射对偶凸形）.

一般的传输映射都可以被唯一地分解成最优传输映射和保Lebesgue测度的映射，. 所有保Lebesgue测度的映射构成一个Lie群。这是著名的Brenier极分解定理。

考察凸曲面嵌入在之中，高斯映射将每一点映射到其法向量上。由于曲面的凸性，高斯映射可逆，于是曲面被球面参数化. 曲面的高斯曲率定义在球面上，Minkowski问题(type II)就是由高斯曲率求得曲面. 在离散情形，这等价于给定凸多面体每个面的法向量和面积，反解凸曲面。Minkowski问题解的存在性可以由体积变分得到，唯一性由Brunn-Minkowski不等式得到。

如果我们将凸曲面进行极坐标表示

将高斯曲率定义在单位球面上，即映射将高斯球面上的Hausdorff测度拉回到定义域的球面上，Minkowski问题（Type I)就是由此高斯曲率测度来重建凸曲面。我们令球面的面积测度和高斯曲率测度为初始和目标测度，传输代价函数为，则最优传输映射为，凸曲面为Kantorovich势能函数的图。

最优传输理论可以直接应用于光学透镜设计问题，这里入射光强和折射光强为定义在球面上的测度，传输代价取决于光学器件本身的设计要求，和介质的光导系数，支撑曲面为旋转抛物、椭球或者双曲曲面，势能函数为支撑曲面的包络，映射满足光学的折射定律。

如果我们将Minkowski（Type II）中的封闭曲面推广为开放曲面，则Minkowski问题推广为Alexandrov问题。Alexandrov问题与Brenier问题等价，都由Monge-Ampere方程所表达。我们可以用最优传输理论来证明解的存在唯一性，也可以用几何体积变分法证明，或者基于代数拓扑的Alexandrov映射引理来证明。如果用Kantorovich对偶问题来描述，Alexandrov问题对应的传输代价为， c-变换为经典的Legendre变换，支撑曲面为平面，势能函数等于支撑平面的上包络（upper envelope），其Legendre对偶为支撑平面对偶点的下凸包（lower convex hull）. 上包络在平面的投影为nearest power diagram，凸包的投影为nearest weighted Delaunay 三角剖分。Power diagram和Weighted Delaunay 三角剖分彼此互为Poincare 对偶。由此，我们看到Alexandrov问题与经典计算几何的紧密联系。

由计算几何的观点出发，我们可以得到最差传输的理论框架。如果我们选取保测度映射中总传输代价最大者，则我们得到最差传输映射。在最差Alexandrov问题中，势能函数对应着支撑平面的下包络（lower envelope）,其Legendre对偶对应着支撑平面对偶点的上凸包（upper convex hull），它们在平面上的投影对应着farthest power diagram和farthest weighted Delaunay 三角剖分。

由凸几何的观点，我们可以深入理解最优传输映射的奇异点集合。最优传输映射的奇异集合是深度学习中生成模型模式坍塌的本质原因。由循环单调性，我们得到最优传输映射的倾斜性条件。我们定义了法向Frechel距离，如果和的法向Frechet距离大于, 则最优传输映射一定存在奇异集合。由此得到若平面曲线有一段总曲率小于，为凸曲线，则最优传输映射必然存在奇异点。我们进一步证明最优传输映射的奇异集合可以用的Power中轴来逼近，从而与经典的中轴同伦等价。

流体力学有Euler和Lagrante观点，Euler方法研究流场的密度和流速，Lagrange方法研究每个粒子的轨迹, 其初始位置为，终止位置为，如此我们得到流场所诱导的单参数微分同胚族，

依赖时间的最优传输问题是寻找流场，是的单参数微分同胚族极小化总的传输代价（即所有粒子轨迹的总长度）

考察严格凸传输代价函数，，路径的长度定义为：

从Lagrange观点来看，最优传输的每个粒子都是匀速直线运动，McCann得到了对应的流场动力学方程为：

第一个方程表示每个粒子的加速度为;第二个方程是质量守恒的连续性方程。这组方程并没有反映出传输代价的不同，这一信息被速度场的初始条件所确定。

Benamou-Brenier考察了流场的作用（总动能），

流场的最小作用定理表明总动能最小的流场，是依赖时间最优传输问题的解，这是.

流体力学的观点讲最优传输理论与无穷维黎曼几何理论相联系，为Wasserstein空间中定义了黎曼度量和协变导数，从而为深度学习中的变分法奠定理论基础。我们先考察不可压缩流场的Euler方程

第一个方程表示粒子受力等于压强的负梯度；第二个方程表示速度场散度为，即不可压缩。考察单参数微分同胚族，由关系

我们得到无散场诱导保Lebesgue测度映射。我们记所有保Lesbesgue测度的同胚构成的Lie群为，任意给定，我们定义它们之间的距离为：

则中的切向量为上的无散矢量场. Euler方程中的第一个等式表示轨道的加速度向量是上的梯度场，梯度场与无散场垂直，因此轨道的加速度与切空间垂直，为测地线。因此Arnold理论宣称Euler方程是保Lebesgue测度同胚Lie群的测地线方程。

类似的，Otto理论将Benamou-Brenier公式解释成Wasserstein空间的测地线方程. 给定密度场，我们定义切空间中的内积，

可以证明，最优矢量场一定是梯度场，即存在函数，

给定切向量，

它们的内积为

Benamou-Brenier最小作用原理得到的解就是在Otto黎曼度量下的测地线。用Otto观点得到的熵流与信息学所得的熵流方程相同。

我们讨论了几乎所有现存的计算方法。最优传输映射满足经典的Monge-Ampere方程

FFT-OT算法

不动点算法（FFT-OT） 在二维情形，我们记，我们定义算子

那么，Brenier势能函数是上面算子的不动点，可以通过迭代法逼近。计算过程中的每一个都等价于求解一个Poisson方程，倾斜性边界条件转化为Neumann边界条件。Poisson方程可以用有限差分方法求解，并且用快速Fourier变换来加速。

连续性方法当时，算子线性化：

这里Hessian矩阵的伴随矩阵. 我们求解Monge-Ampere方程，定义密度流

相应的Brenier势能是，我们得到

令，我们得到

倾斜性条件转化成Neumann边界条件，在时刻，.

Tannenbaum算法 我们先找一个保测度映射，依随时间演化，逐步减小Monge传输代价. 构造微分同胚 ，保持测度不变，，将复合，使得的传输代价减小。由传输代价

去掉的散度分量，

设置速度场。这一算法高维情形的充分性依然缺乏证明。

几何变分法 Alexandrov定理等价于半离散最优传输映射。假设的密度函数绝对连续，为Dirac测度之和，

满足条件，传输代价为欧氏距离的平方. 对于每一个采样点，我们构造一个支撑平面，这里高度待定，Brenier势能函数是支撑平面的上包络

上包络投影得到Power Diagram

每个胞腔的体积为, 传输映射为, . 每个支撑平面的对偶点为，Brenier势能函数的Legendre对偶是对偶点的凸包. 算法归结为在可容许高度空间

中，优化凸能量

其梯度等于

Hessian矩阵

这里是Power Diagram中胞腔和交界的边，是其对偶的Weighted Delaunay边.

这种方法可以直接推广到其他黎曼度量情形。基于几何变分原理的最优传输算法的实现非常具有挑战性，核心难点在于：

• 复杂的组合数据结构，我们介绍了单纯复形的半边数据结构和一般复形的Dart数据结构，并且提供了功能完善的库；
• 算术计算的精度，传统的双精度计算无法保证算法的鲁棒性；理论完美的算法经常由于计算误差而崩溃，这需要用到自适应精度的算术运算的方法.

我们将平面Voronoi Diagram和Delaunay三角剖分，三维空间的Voronoi Diagram和Delaunay三角剖分，平面最优、最差传输映射，球面最优传输映射分别作为作业，提供了详尽的算法解释和Skeleton源代码，帮助听众练习掌握。