最优传输理论的全局几何观点
最近很多年轻朋友询问最优传输的理论和计算问题。当年丘成桐先生是通过凸微分几何的Minkowski问题教给笔者Monge-Ampere方程的相关理论，因此笔者一直通过几何图景来理解最优传输和Monge-Ampere方程。最优传输理论具有非常直观的几何图景，并且与经典的计算几何概念和理论密切吻合。例如经典的Brenier理论等价于Minkowski-Alexandorff凸几何理论（图9），c-变换等价于几何中的包络。最优传输中的各种对偶与几何中的各种对偶一一对应：c-变换（勒让德变换）对应包络、凸包直接的对偶（图3，图4），正逆最优传输变换对应Power diagram与Weighted Delaunay之间的对偶（图2，图6），最优传输与最差传输对应上包络与下包络的对偶（图2，图7，图8）。
图1. 弥勒佛曲面通过黎曼映照映射到单位圆盘，从而将曲面面元推前到圆盘，作为最优传输的源测度。
绝大多数最优传输领域的研究专注于求解一个映射，或者Monge-Ampere方程。这里我们介绍整体几何图景（图10）：即所有的Brenier势能函数构成的无穷维泛函凸空间, 所有的目标测度构成无穷维凸空间，最优传输映射诱导了两个空间之间的微分同胚,这个映射逐点由Monge-Ampere方程所确定。我们可以看到，在经典的半离散Brenier最优传输框架下，Brenier势能函数空间有天然的Power Digram剖分（Power Diagram的Power Diagram），目标测度构成的空间具有相应的Secondary Polytope结构（三角剖分的三角剖分），这两个泛函空间之间的映射是分片多项式的，并且映射的雅克比矩阵具有鲜明的几何解释。所谓的求解最优传输映射过程可以被理解为同伦过程：给定曲线段，求其在中的原像，通过求解雅克比矩阵的逆，原像曲线可以逐点被追踪延拓。这种整体的几何图景，为最优传输问题的计算提供了新颖的视角。
在AI生成模型中（例如GAN模型、Diffusion模型），每个数据样本（例如某类图像）被视为高维背景空间中的一个点，整个数据集被视为一片稠密点云，这片点云在某个流形附近，即所谓的数据流形，而数据集代表的点云被视为数据流形上的一个概率分布（概率测度）。深度学习的核心任务就是学习流形结构和流形上的概率分布。编码映射将数据流形映射到隐空间，解码映射将隐空间映回数据流形。因此，数据流形的拓扑结构由编码映射和解码映射所表达，而编码、解码映射由深度神经网络来参数化。编码映射将数据流形上的分布映射到（推前）隐空间的数据分布，即所谓的隐数据分布。我们用计算机通过伪随机数生成均匀分布（或者正态分布）即白噪声，然后计算一个传输映射，将白噪声变换成隐数据分布，由此数据分布被传输映射所表达，而传输映射也由深度神经网络所参数化。例如，在GAN模型中，生成器计算从白噪声到数据分布的传输映射，判别器计算从数据分布到生成分布之间的最优传输映射，而Diffusion模型计算数据分布到正态分布之间的传输映射（以及逆映射）。由此可见，最优传输为生成式AI奠定了理论基础。
Monge-Kantorovich问题
如图1和2所示，给定欧氏空间中的源区域，以为支集的概率分布，具有密度函数；目标区域，以为支集的概率分布，具有密度函数，一个映射被称为是保测度的，如果对于任意波莱尔集合，都有
保测度条件记为。给定传输代价函数，代表从点传输单位质量到的代价，映射的总传输代价为：
著名的Monge问题是在所有保测度的映射中，寻找总传输代价最小者：
最优传输映射的总传输代价定义为和之间的距离。
Kantorovich将传输映射放松成传输方案，即定义在乘积空间上的联合概率分布，其边际分布等于和，即，，这里投影映射为，。Kantorovich问题转化为：
更进一步Kantorovich问题等价于Kantorovich对偶问题：
这里是的c-变换（经典勒让德变换的推广），
图3. c-变换等价于求取下包络。
c-变换具有鲜明的几何意义：包络。如图3所示，固定任意的，我们定义函数，图中黑色曲线；变动，我们得到一族函数。这族函数图像的包络就是，即图中的红色曲线。等价地，我们可以说每一条都是的支撑曲线。考察点，红色曲线与蓝色曲线相切，那么最优传输映将映成。我们称和为Kantorovich势能函数。如果我们能够计算c-变换，那么就可以直接优化Kantorovich对偶能量，势能函数对序列为：
对于特定的传输代价函数，我们有，因此优化在有限步骤内终止。因此，我们看到几何上的包络是计算中的核心问题。
最优性初等证明
我们可以将目标测度用离散测度（即狄拉克测度之和）来逼近，设
定义在上的Kantorovich势能函数记，，满足归一化条件
那么Kantorovich势能函数等于
诱导的一个胞腔分解，
对偶问题的能量可以写为：
假设在时，能量达到最大，这时
即胞腔的-体积等于；最优传输映射为
即每个胞腔映射到一个目标点。
我们下面证明这个传输映射的最优性。假设存在另外一个胞腔分解， 满足，传输映射,，那么我们直接比较总传输代价，
这就证明了传输映射的最优性。
Brenier定理
如果传输代价函数是欧氏距离的平方，Monge问题表述为
因为，所以，上式前两项与映射无关. 由此，上面的Monge问题等价于下面的问题
这时，传输代价函数为。对偶问题表述为
这时变换为经典的勒让德变换，
这意味着是的支撑平面，梯度为。
图4. 函数的凸化：两次勒让德变换，等价于求函数图像支撑平面的上包络。
如图4所示，从几何上看，是的所有支撑平面的上包络，即包含的图像是包含图像的最小凸集（凸包）。如果为凸函数，则。
固定，设右侧在达到极大值，这时关于的梯度为零，，由此我们得到
同时，即等于自身两次勒让德变换，从而为凸函数。
图5. 图解Brenier定理。
由此，如图5所示，我们得到经典的Brenier定理：当时，最优传输映射等于某个凸函数的梯度映射，，这个凸函数被称为是Brenier势能函数，同时由，我们有, ，即得到Monge-Ampere方程：
各种几何对偶性
为了方便将具体概念可视化，我们定义半离散最优传输Brenier问题：设是凸紧集，是经典的勒贝格测度, 目标测度为离散测度，Brenier问题的对偶表示为 ,
这里是的Nearest Power Voronoi Diagram，
图6. 各种对称性，总结为最优传输局部几何观点口诀：代价变换支撑，支撑包络势能，势能微分映射，映射对偶凸形。
如图6所示，我们看到每个目标点对应一张支撑平面，Brenier势能函数
是支撑平面族的上包络，上包络在上的投影是Power Diagram。更进一步，，可以视作是点集的凸包，这里是支撑平面的对偶。凸包的投影，得到点集的Nearest weighted Delaunay三角剖分。最优传输映，等于上包络的切映射；其逆（广义）映射也是最优传输映射，，等于凸包的广义梯度映射。这里，我们看到了很多几何上的对偶，支撑平面族的上包络与支撑点集的凸包对偶，nearest Power Voronoi diagram和 nearest weighted Delaunay triangulation对偶，最优传输映射与最优逆映射对偶。
图7. Brenier定理推广到最差传输。
还有一个更加隐密的对偶，最优传输与最差传输的对偶，几何上这等价于支撑平面族上包络和下包络的对偶。所谓最差传输问题就是在所有保测度映射中，寻找总传输代价最大者：
如果，Brenier定理依然成立，即存在凸函数，最差传输映射等于的梯度映射，满足Monge-Ampere方程。如果目标测度是离散测度，，对于每个目标点，我们构造支撑平面，这些支撑平面的下包络
下包络对偶于的凸包。下包络的投影得到的farthest power Voronoi diagram
其对偶的三角剖分得到farthest weighted Delaunay triangulation。
图8. 上下凸包对偶下上包络，对应着最优和最差传输。
存在、唯一性几何证明
半离散Brenier定理与经典的凸几何Alexandroff定理等价。给定平面上的凸区域，是中的开放凸多面体，具有个面，每个面上的法向量给定，任给个正数， 其和等于的总面积，,设第个面的线性方程为，则存在，使得第个面在上的投影面积等于。并且这种凸多面体彼此相差一个铅直平移。因此，我们可以从Alexandroff定理推出Brenier定理中的存在性和唯一性。
图9. Alexandroff 定理，与Brenier定理等价。
下面我们给出更加简单直接的推导过程。
考察半离散Brenier能量：
直接计算，得到其梯度为
这里是Power Voronoi 胞腔的体积。进一步计算能量的Hessian矩阵：
这里的分子是Power Diagram中的一条边，分母是Weighted Delaunay triangulation的对偶边。由得到：
我们看到Hessian矩阵在线性子空间上是严格负定的，因此能量严格凹。
我们定义所有可能的势能函数构成的空间：即所有的使得所有Power Diagram胞腔非空，
首先，非空。不失一般性，我们假设，那么存在的Voronoi Diagram，这时
这意味着
因此非空。的凸性需要用到Brunn-Minkowski不等式：假设是欧氏空间中的凸集，则
这里是和的Minkowski和：
是的勒贝格测度。如果，则所有的Power 胞腔, ，由Brunn-Minkowski不等式，
因此，为中的维紧凸集。
能量在紧凸集上可微，必然存在达到最大值。如果，则存在一个Power 胞腔，偏导数，指向的内部，因此必为的内点，从而，
因此，解存在。由在上强凹，最大值唯一，因此解唯一。这就证明了最优传输映射的存在性和唯一性。
存在唯一性也可以用几何方法来直接证明。Brenier势能决定了Alexnadroff凸多面体，即支撑平面集合的上包络与圆柱体的交集，然后再与半空间求交。考察下面的优化问题：在超平面与的交集上，求的最大体积，由Lagrange乘子法：
在的内点处取到最大，则
因为， . 假设存在两个最大值，和体积相同，则由Brunn-Minkowski不等式, 体积更大，从而得到矛盾。
最优传输的全局几何图景
从上述讨论中，我们看到每次计算最优传输映射，从几何上看主要是在计算凸包和其对偶的上包络
图10. 最优传输的全局几何观点：Brenier势能函数空间到离散测度空间的微分同胚，最优传输问题等价于同伦追踪问题。
我们将所有的最优传输映射从全局角度来考虑，所有的离散Brenier势能函数构成凸紧集，相应的所有的离散测度构成一个维单纯形：
每一个Brenier势能函数映射到某个离散概率测度，这里等于Power 胞腔的体积， 为最优传输映射，由此定义了整体映射，这个映射是微分同胚，其雅克比矩阵为
给定目标测度，我们希望得到相应的Brenier势能函数。我们首先构造的Voronoi Digram，得到，和相应的 ，然后连接和得到线段。我们希望求得在下的原像，我们知道的雅克比矩阵，可以局部用来线性逼近，由连续性方法（同伦方法）:
我们可以一步一步从追踪到。每一步等价于求解一个Possion方程：
这里雅克比矩阵的系数是变系数的。主要的计算困难是步长的选择，使得在追踪过程中，追踪路径一直在内部，一旦越界立刻返回。如何选择是计算稳定性的关键。理论上，是紧集，是微分同胚，是紧集，到的距离为, 沿着，的Hessian矩阵的最小特征根为, 其下界为，那么步长
可以保证搜索过程中不越界。实际应用中，我们并不事先知道距离和特征根的下界，因此算法实现中需要试探和回溯。理论上，这里的微分同胚本质上是次分片多项式的，我们可以计算高阶导数，从而得到精确估计。但是迄今为止没有人认真地计算过这些分片多项式，核心原因在于Secondary Polytope过于复杂。
另一个困难是计算过程中，Power Diagram和Weighted Delaunay Triangulation的组合结构是动态变化的。一个基本的问题是在每个计算过程中，三角剖分变化多少次？这要用到盖尔芳德的Secondary Polytope理论，这一理论可以被概括成“三角剖分的三角剖分”。设是两个势能函数，如果它们诱导的在上的Weighted Delaunay triangulations 为和，如果和相同，那么它们彼此等价。每个等价类构成一个胞腔，对应的一个三角剖分，记为，如此我们的的一个胞腔分解：
我们证明这个胞腔分解是Power Diagram，即Power Diagram的Power Diagram。
图11. 盖尔芳德的Secondary Polytope理论，即三角剖分的三角剖分，每个三角剖分抽象成一个点，这些点的凸包表达了所有的三角剖分，凸包边界处的三角剖分为加权Delaunay三角剖分。Discrete and Computational Geometry，S. Devadoss and J. O'Rourke.
如图11所示，我们固定目标采样点集, ，的凸包记为。我们考察所有以为顶点的、可能的三角剖分。我们为每一个这样的三角剖分赋予一个特征向量（characteristic vector），的单纯形记为，如果是的一个顶点，那么记为，
点集的secondary polytope 定义成所有特征向量的凸包【2】：
如果一个三角剖分，其特征向量在 边界上，那么是某个下的Weighted Delaunay triangulation; 如果 和在中有一条边相连，则和彼此相差一个Stellar 变换，在二维情形和彼此相差一个Edge swap. 凸包的对偶是定义在上的上包络
上包络的投影得到的Power VoronoiDiagram，每个胞腔对应一个Weighted Delaunay triangulation ，满足
由盖尔芳德secondarypolytope理论【2】，所有可能的Weighted Delaunay Triangulation 个数为，的直径为, 这给出了最优传输映射的计算过程中，三角剖分组合结构变化的次数。我们看到盖尔芳德的secondary polytope（三角剖分的三角剖分）对偶于Brenier势能函数空间的Power Diagram（Power Diagram的Power Diagram）；根据Brenier定理，我们得到映射，是最优传输映射；具体细节可以参考【1】。目前对于这个二次元power diagram的算法研究几乎一片空白, 我们期待这方面的研究能够有所突破。
目前，在AI领域和计算机科学领域，人们只计算最优传输映射的弱解，而对于解的正则性讨论很少。而Monge-Ampere方程的正则性理论，需要更多更深刻和微妙的几何洞察。在未来，当计算机科学发展进一步深入，最优传输正则性理论的几何图景将会渗透进来。
小结
这里，我们总结了最优传输理论的几何观点，包括局部观点和整体观点。从局部上来看，求解一个最优传输问题的口诀是“代价变换支撑，支撑包络势能，势能微分映射，映射对偶凸形”，这里涉及到大量的对称性，可以从分析和几何两个角度来理解，勒让德变换对应上包络与凸包的对偶，正逆最优传输对应Power Diagram和Weighted Delaunay的对偶，最优最差传输对应上包络和下包络的对偶，通用c-变换对应于曲面族包络等等。
图12. Power Voronoi Diagram 与 Weighted Delaunay Triangulation 对偶，自然出现在最优传输的局部几何观点和全局几何观点之中。
从整体上看，最优传输给出了所有Brenier势能函数构成的空间到所有测度构成的空间之间的微分同胚，其雅克比矩阵由Power Voronoi 边长与Weighted Delaunay 边长之比给出，进一步这个微分同胚是分片多项式的；所有可能的Weighted Delaunay 三角剖分的特征向量的凸包，构成盖尔芳德的Secondary Polytope，即所有三角剖分的三角剖分，其对偶是所有Power Diagram的Power Diagram，即所有势能函数构成的空间的Power Diagram，每个胞腔对应一个三角剖分。相对于局部几何观点，整体几何观点尚未被广泛探索，具有广阔的研究前景。
致谢
感谢丘成桐院士的教导，感谢罗峰教授，汪徐家教授，赵国辉教授等数学家，与他们的深入探讨启发了我们的工作【1】；感谢所有的合作者和同学们。封面 credit: @GIORDANOPHOTOGRAPHY ON INSTAGRAM
【1】Na Lei, Wei Chen*, Zhongxuan Luo, Hang Si, Xianfeng Gu. Secondary Polytope and Secondary Power Diagram. Computational Mathematics and Mathematical Physics, 2019,59(12):1965-1981.
【2】M. Gel’fand, M.M. Kapranov, and A.V. Zelevinsky. Discriminants, Resultants, and Multidi-mensional Determinants. Birkhauser, 1994.
请长按下方二维码，选择 “识别图中二维码”，即可关注。
【老顾谈几何】邀请国内国际著名纯粹数学家，应用数学家，理论物理学家和计算机科学家，讲授现代拓扑和几何的理论，算法和应用。