本页只解决一个问题

输运矩阵的行列约束是什么，势函数怎样给出对偶问题？

本页是原长篇讲义的单概念版本。第一次阅读只追踪本页定义的对象；看见未掌握的前置符号时，先沿链接退回，不要跳过定义硬背结论。

开始前

• 模块前置入口：先修页面
• 本页所属模块：最优输运与几何深度学习
• 集中复习版：原长篇参考讲义

4. 离散最优输运

设

$$\mu=\sum_{i=1}^na_i\delta_{x_i}, \qquad \nu=\sum_{j=1}^mb_j\delta_{y_j},$$

其中$a_i,b_j\ge0$ 且总和相等。输运矩阵$P\in\mathbb R_+^{n\times m}$ 满足

$$P\mathbf1_m=a, \qquad P^T\mathbf1_n=b.$$

代价矩阵$C_{ij}=c(x_i,y_j)$。线性规划：

$$\min_{P\ge0}\langle C,P\rangle \quad\text{s.t.}\quad P\mathbf1=a, P^T\mathbf1=b.$$

变量数为$nm$，大规模直接 LP 很贵。

5. Kantorovich 对偶

给边缘约束引入势函数$\varphi_i,\psi_j$。Lagrangian：

$$\mathcal L(P,\varphi,\psi) =\sum_{ij}C_{ij}P_{ij} +\sum_i\varphi_i(a_i-\sum_jP_{ij}) +\sum_j\psi_j(b_j-\sum_iP_{ij}).$$

整理：

$$\mathcal L =\varphi^Ta+\psi^Tb +\sum_{ij}(C_{ij}-\varphi_i-\psi_j)P_{ij}.$$

为了使$\inf_{P\ge0}\mathcal L$ 有限，必须

$$\varphi_i+\psi_j\le C_{ij}.$$

于是对偶问题：

$$\boxed{ \max_{\varphi,\psi} \varphi^Ta+\psi^Tb \quad\text{s.t.}\quad \varphi_i+\psi_j\le C_{ij}. }$$

互补松弛：若$P_{ij}>0$，则

$$\varphi_i+\psi_j=C_{ij}.$$

读完必须能回答

1. 不看公式，用自己的话回答开头的核心问题。
2. 指出本页最重要公式中每个符号的类型：标量、向量、矩阵、映射还是集合。
3. 找出定理成立所需的假设，并举一个删除某条假设后可能失败的例子。
4. 对最小例子手算一遍；若本页含代码，再比较手算与程序输出。

前后课程

上一课：Monge 问题与 Kantorovich 松弛 ｜ 下一课：Wasserstein 距离与 W1 对偶