最优传输 I · 从搬运计划到最优性证书

1. 固定边缘，改变的是配对关系

给定概率测度 \(\mu,\nu\)，耦合 \(\pi\in\Pi(\mu,\nu)\) 是边缘分别等于它们的联合分布。边缘告诉我们两边各有多少，耦合告诉我们谁与谁相连。乘积测度 \(\mu\otimes\nu\) 总是一个可行耦合，但通常不是最便宜的配对。

Monge问题选可测映射 \(T\)，满足 \(T_\#\mu=\nu\)，即对每个可测集合 \(B\) 有 \(\mu(T^{-1}(B))=\nu(B)\)；它的计划是 \((\mathrm{id},T)_\#\mu\)。同一个源点只能有一个目标。

Kantorovich问题直接选耦合：

每个Monge计划都在这个集合里，所以允许拆分的最小值不大于Monge最小值。这里“松弛”先指扩大可行集合；对于任意原子源，不能进一步假称映射计划在所有耦合中稠密。

若源为 \(\delta_0\)，目标为 \(\tfrac12\delta_{-1}+\tfrac12\delta_1\)，映射无解，耦合却唯一且可行。即使映射可行，原子质量的整份分配限制仍可能导致严格的最优值差；第11节给出具体算例。基本对象和这一原子障碍可参阅 Santambrogio导论第1.1节。

2. 有限运输表：可行集为何既非空又有最小值

令 \(a_i,b_j\geq0\)，两侧分别合计为1，成本 \(C_{ij}\) 为有限实数。变量 \(P_{ij}\) 是从源标签 \(i\) 运到目标标签 \(j\) 的质量。原始问题为

\(P=ab^\top\) 给出非空性。每格 \(0\leq P_{ij}\leq1\)，约束集闭且有界，因此紧；线性目标连续，最小值取得。一般成本可以为负，仍不会使这个有限问题无界，因为总质量固定。但负成本或不对称成本下，最优值一般不是距离，不能随意称为 \(W_1\)。

同侧若两个标签其实是同一个空间位置，应先合并它们的质量，再讨论“一个位置只能有一个去处”。实验的几何模式会要求同侧位置不同，以免把重复标签误当成两个可独立选择的原子。零质量标签可保留，但不增加实际运输任务。

3. 报价为何能证明一个下界

对边缘约束引入乘子 \(\phi_i,\psi_j\)，拉格朗日式是

对所有非负 \(P\) 取下确界：若每格系数非负，结果为 \(a\cdot\phi+b\cdot\psi\)；若某格为负，可以让那一格无限增大，结果为 \(-\infty\)。注意这里已把边缘约束移到乘子里，内层不是原始运输多面体。

因此对偶为

任意可行报价都不超过任意可行搬运方案的成本。这是弱对偶，直接乘以 \(P_{ij}\geq0\) 后求和即可证明。有限线性规划的强对偶进一步保证两端最优值相等且取得；适用条件已经由第2节的非空与有限最优值核对。完整有限推导见 Peyré的离散对偶讲义。

经济直觉可以帮助记符号：供给端和需求端各报一份价，总价不得高过该路线的实际成本。它是最优性的价格证书，不是运输质量本身。

4. 差额恒等式：先可行，再谈最优

记每格剩余量 \(s_{ij}=C_{ij}-\phi_i-\psi_j\)。对任意两端可行对象，

因此零差额等价于两端同时最优；又因每项非负，等价于逐格互补松弛：

反过来 \(s_{ij}=0\) 并不要求 \(P_{ij}>0\)。紧边只允许承载质量，还要兼顾其他行列。所有成本相同的例子中每条边都可紧，但一份最优计划仍可有零格。

如果提交的计划不满足边缘，令 \(r=P\mathbf1-a\)、\(t=P^\top\mathbf1-b\)，真正的恒等式是

实验保留这两项残差修正，不把总价相等当成自动合格。负质量、错误边缘、不可行报价分别标记；它们是候选对象的诊断状态。只有质量非负、边缘精确相等、全部 \(s_{ij}\geq0\) 且差额为零时，才给出精确最优证书。

平移 \((\phi,\psi)\mapsto(\phi+u\mathbf1,\psi-u\mathbf1)\) 不改变任何总报价与slack；因为两边总质量相同，对偶收入也不变。所以势至少有这一个表示自由度，不能把显示出的向量宣称为唯一答案。

5. 为什么可以检查全部顶点，而不能只数基

把正质量格看成二部图的边。若它们包含一个环，就能沿环交替加减足够小的 \(\epsilon>0\)，得到两个不同可行计划，其平均为原计划。因此含正环的计划不是顶点。反之，森林支持上的边缘方程沿叶子逐步确定质量，不可能再分解为两个不同的可行计划。

有限运输多面体的顶点由无环支持刻画。把森林添上零质量边，可以扩展到一棵覆盖全部 \(m+n\) 个标签的生成树；树有 \(m+n-1\) 条边。实验枚举这些树，用边缘方程精确消元，筛出非负计划，再去重。

一个顶点可能对应多棵基树。 退化时某些基边质量为零，换一条零边仍可描述同一个计划。于是“有几个可行基”不等于“有几个不同顶点”，更不等于“有几个最优计划”。当最优顶点有两个以上，它们之间的凸组合也都最优，通常是无穷多组；只有一个最优顶点时，整个最优面才缩成一个点。

实验还枚举原子映射 \(j(i)\)，计算每个目标收到的 \(\sum_{i:j(i)=j}a_i\)。零质量源行的标签选择不额外计数。这样可以直接比较映射可行性、最优映射成本与Kantorovich值，而不凭网络外观猜测。

等数量、等权重 \(1/n\) 时，缩放矩阵 \(nP\) 是双随机矩阵，其顶点是置换矩阵。可接着用森林证明：缩放后的边缘全为整数1，沿叶消元使每条基边质量都是整数；非负且每行每列和为1，只可能各有一个1。这种特殊情形保证存在一个置换型最优解；成本平局时仍可能同时有拆分的最优解。一般不等质量情形不能套用这一结论。

6. c变换：最大可行回复，不是全局求解器

固定 \(\phi\)，目标势每列都必须满足 \(\psi_j\leq C_{ij}-\phi_i\)，故最大的可行回复是

若原来的 \((\phi,\psi)\) 已经可行，替换成 \((\phi,\phi^c)\) 不降低对偶目标。若原报价不可行，修复后收入可能下降，这正是在去掉违法报价。接着反向变换 \(\phi^{c\bar c}_i=\min_j(C_{ij}-\phi^c_j)\)，同样保留可行性。

两次变换闭合仍不必全局最优。默认问题中取 \(\phi=(0,0)\)、\(\psi=(1/4,1/4)\)，双方已互为这样的回复，对偶收入却只有 \(1/4\)，而最优值是 \(3/4\)。这个操作帮助整理势与证明紧性，不能单凭“回复已不变”验收全局最优。

连续版本是 \(\phi^c(y)=\inf_x[c(x,y)-\phi(x)]\)，记清楚是下包络。按凸共轭 \(f^*(y)=\sup_x(\langle x,y\rangle-f(x))\) 的约定，若 \(c(x,y)=\langle x,y\rangle\)，则

若采用半平方成本 \(c(x,y)=\tfrac12|x-y|^2\)，令 \(u(x)=\tfrac12|x|^2-\phi(x)\)，则

这里剥离二次项以后才出现通常的凸共轭。实验的平方成本是完整 \(|x-y|^2\)，其目标值是 \(W_2^2\)，不要漏掉因子或开方。

7. 从有限表到连续定理，哪些条件不能省略

一个清楚、够用的版本是：\(X,Y\) 为紧致度量空间，\(\mu,\nu\) 为Borel概率测度，\(c\in C(X\times Y)\) 为有限连续成本。此时最优耦合存在，且

原始取得最小值的理由是：固定边缘的耦合集弱闭、在紧乘积上紧，目标对弱收敛连续。对偶等值不能仅靠形式上交换 \(\inf\) 与 \(\sup\)；可以用凸分离证明。对一个低于原始最优值的数，分离“可实现边缘与成本上图”的闭凸锥，归一化分离泛函后就得到收入高于该数的可行势，最后逼近最优值。

对偶的最大值也需另证。对最大化序列作两次c变换，再固定一个源点的势为零。变换继承成本在两变量上的一致连续模，并给出统一有界性；Arzelà–Ascoli产生一致收敛子列，极限仍可行且达到最大值。参阅 Peyré：连续对偶及取得性 与 Santambrogio书中第1.6节。

在Polish空间上，非负下半连续成本已足以使原始扩展实数最小值取得；若要有限值，还需有有限成本的可行耦合。非紧、无界成本下的对偶函数类、可积性与取得性要重新核对，不能把上面的连续势最大值公式无条件搬过去。

连续互补松弛先给出 \(c=\phi+\psi\) 在最优耦合下几乎处处成立；在这里的连续条件下，才能进一步延伸到整个支持。这个接触集合不是说其中每一点都一定运质量。

8. 一维分位数：单调可以拆分，最优未必都单调

定义广义分位数 \(F_\mu^{-1}(u)=\inf\{x:F_\mu(x)\geq u\}\)，\(0\lt u\lt1\)。若 \(U\) 均匀分布于 \((0,1)\)，则

给出共同分位数耦合。在原子模型中，把源质量和目标质量分别排成长度为1的区间；两个原子区间交叠多少，就在对应格运多少。实验列出每段交叠的左右端点、质量与两个位置。

对非负凸函数 \(h\) 的成本 \(c(x,y)=h(y-x)\)，在最优值有限时，这个耦合最优；严格凸时它还是唯一最优耦合。源无原子时，才可把它写成映射 \(T=F_\nu^{-1}\circ F_\mu\)（几乎处处）。有原子时，一个源区间可能与多个目标区间相交，所以单调并不禁止拆分。定理及条件见 Santambrogio第2.2节，定理2.9。

有限模型的交换计算说明机制。对 \(x_1\lt x_2\)、\(y_1\lt y_2\)，平方成本有

把交叉两边共同的一小份质量改成不交叉，边缘不变，成本严格下降。一般凸成本给出非严格不等式。

绝对距离存在取等：源在0、1，目标在2、3时，全部路线都有 \(|x-y|=y-x\)。任意可行耦合的成本都是 \(\mathbb EY-\mathbb EX=2\)，交叉与不交叉都可以最优。于是“存在单调最优解”不等于“所有最优解都单调”。

对 \(p\geq1\) 且两分布具有有限 \(p\) 阶矩，

这是距离幂成本的公式；一般凸 \(h\) 应保留 \(h\)，不把它都命名为同一个 \(W_p\)。

9. W1的第三种读法：最会区分分布的平缓函数

在同一个度量空间上令 \(c=d\)。若 \(f\) 已经1-Lipschitz，则 \(d(x,y)-f(x)\geq-f(y)\)；取 \(x=y\) 又达到这个下界，所以 \(f^c=-f\)。前提是同一个空间与真正的距离成本，不能对任意势或任意成本直接套这句话。

Kantorovich–Rubinstein对偶给出

非紧空间通常要求有限一阶矩，并可固定 \(f(x_0)=0\)，保证积分有意义。c变换证明与有限检验函数约束见 Peyré：Wasserstein-1。

一维有限原子例尤其直观。把两侧所有位置合并排序为 \(z_0\lt\cdots\lt z_K\)，记区间上的累积质量差 \(A_k=F_\mu(z_k)-F_\nu(z_k)\)。则

构造 \(f(z_0)=0\)，并令

相邻斜率不超过1，累加后所有点对都满足Lipschitz约束。离散分部求和给出

它恰好达到分位数计划的成本，于是既有一份可行搬运方案，又有一份同价的检验函数证书。一般一维有限一阶矩情形对应 \(W_1=\int_{\mathbb R}|F_\mu-F_\nu|\,dx\)；相关CDF与分位数面积恒等式见 Santambrogio命题2.17。

10. 环形交换：两两不改善还不够

对一个最优计划支持中的有限配对 \((x_i,y_i)\)，对偶接触条件求和可得，对任意排列 \(\sigma\)，

这称为c循环单调性。它检查所有长度的循环；一般成本矩阵中，只检查两对交换不足以代替它。第11节的三乘三例子中，每次两两互换都增价，三条边一起轮换却能降价。

有限网络还可用残余环解释：给当前正质量边加入允许撤回的反向边。若存在负成本的可行残余环，沿它增广一小份质量就能降价；最优计划不能有这种环。实验以完整基枚举核对最优值，而不是把某一轮局部交换停止当作充分证据。

11. 四道完整练习：把证书写到纸上

练习一：映射明明可行，为何允许拆分仍更便宜？

源质量为 \((3/4,1/4)\)、位置为 \((0,1)\)；目标质量为 \((1/4,3/4)\)、位置为 \((1/4,5/4)\)。用绝对距离成本求Kantorovich计划、证书和最优Monge成本。

练习二：零差额和c变换闭合，各自遗漏了什么？

沿用练习一。先提交 \(P=0,\phi=0,\psi=0\)；再提交正确计划，但用 \(\phi=(0,0),\psi=(1/4,1/4)\)。分别判断。

练习三：同一个W1怎样从CDF和检验函数算出？

仍用练习一的两分布。列出相邻位置区间上的CDF差，构造一份最优1-Lipschitz函数，并求 \(W_2\)。

练习四：三条边一起换，为什么能打破两两检查？

令两侧质量都为 \((1/2,1/4,1/4)\)，成本为

从对角计划出发，比较两两交换与三条边顺时针轮换，并给出最优性证书。

12. 向下一课迁移：距离、映射与数值算法各有边界

最优传输赋予概率分布几何比较，但不会自动解决全部学习或生成问题。支撑不重合时，KL可能为无穷而有限矩条件下的Wasserstein距离仍有限；这是两种对象关注的信息不同。一个数值距离有限，不保证训练算法稳定、采样高效或模型拟合成功。

在真实任务中还要分开：经验分布近似误差、有限优化误差、熵正则引入的偏差，以及模型本身对可实现映射的限制。后续的Sinkhorn算法与Wasserstein几何会逐项引入这些对象。本课先保留最重要的验收顺序：写清允许的配对，核对边缘与非负性，取得可行对偶下界，再用差额证明最优。

下一课：Wasserstein几何与Brenier映射。