最优传输理论Monge-Kantorovich问题的对偶形式

1. 理解原问题：寻找最省力的搬运方案

最优传输的核心问题可以这样通俗地理解：你有两堆沙子，来源分布和目标分布可能形状各异。你想把沙子从源头搬运到目标，使得每粒沙子移动的“总成本”（通常是距离）最小。这就是最优传输。

最初，法国数学家加斯帕德·蒙日 (Gaspard Monge) 在18世纪提出了这个想法。他设想的方案非常直接：为每个源头的沙粒指定一个唯一的目标地，即一个确定的“搬运函数”。用数学语言说，给定两个概率分布 $\mu$ 和 $\nu$，我们希望找到一个映射 $T: X \to Y$，使得当源头分布是 $\mu$ 时，经过搬运 $T$ 后得到的分布恰好是 $\nu$，并且使总运输成本 $\int c(x, T(x)) d\mu(x)$ 达到最小。其中 $c(x, y)$ 表示将一点从 $x$ 运到 $y$ 的成本。

这个称为 Monge 问题 的表述虽然直观，但在理论上存在困难。它对搬运函数 $T$ 的要求非常严格（必须是确定的映射），导致解不一定存在，尤其当源头分布是连续的（如一团烟雾）而目标分布有多个离散点时，无法用单值函数将连续的源头分割给离散的目标。

2. 理解松弛问题：Kantorovich的宏伟突破

为了解决 Monge 问题的局限性，苏联数学家列昂尼德·康托洛维奇 (Leonid Kantorovich) 在20世纪中叶提出了一个革命性的视角转换。他不再要求每个源头点必须完整地去往一个目标点，而是允许“拆分”运输。

你可以这样想象：想象每个源头点不是一粒沙子，而是一小堆可以任意细分的沙粒。搬运方案不再是给每个源头点一个目的地，而是制定一个详细的“运输计划” $\pi$，它明确记录了从源头区域 $A$ 到目标区域 $B$ 之间流动了多少沙子的量。

数学上，这个“运输计划”是一个联合概率分布 $\pi \in \Pi(\mu, \nu)$。这里的 $\Pi(\mu, \nu)$ 表示所有满足以下两个条件的联合分布 $\pi$ 的集合：第一个条件是，对于源头区域，所有从该区域运出的沙子的总量必须等于源头分布 $\mu$ 在该区域的量；第二个条件是，对于目标区域，所有运到该区域的沙子的总量必须等于目标分布 $\nu$ 在该区域的量。

于是，Kantorovich 问题 就变成了：在所有满足上述条件的运输计划 $\pi$ 中，寻找使总运输成本 $\iint c(x, y) d\pi(x, y)$ 最小的那一个。这个更灵活、更一般的框架保证了解的存在性，是现代最优传输理论的标准形式。

3. 引入对偶理论：从正面强攻到侧面迂回

直接求解 Kantorovich 问题（一个在无限维空间上寻找最优分布的极小化问题）通常是困难的。对偶理论提供了一条“迂回”的路径：构建一个与之等价但形式可能更简单、更容易处理的问题。

对偶的基本思想是：对于任何一个满足约束的运输计划 $\pi$，它的成本都可以用另一组变量（称为“势函数”）来给出一个下界。通过寻找这个下界的最大值，我们就有可能得到原问题的最小值。

让我们一步步建立这个对偶形式。

第一步：定义势函数。 假设存在两个函数 $\phi: X \to \mathbb{R}$ 和 $\psi: Y \to \mathbb{R}$，它们被称为对偶变量或势函数。

第二步：构造下界不等式。 观察到一个关键性质：对于任意的 $(x, y) \in X \times Y$，我们总有以下关系成立：
$$ \phi(x) + \psi(y) \leq c(x, y) $$
这个不等式是构建对偶的核心，它建立了成本 $c(x, y)$ 与势函数值之间的联系。

第三步：对不等式进行积分。 将上述点态不等式关于联合分布 $\pi \in \Pi(\mu, \nu)$ 进行积分。由于 $\pi$ 是非负的，不等式在积分后依然保持：
$$ \iint (\phi(x) + \psi(y)) d\pi(x, y) \leq \iint c(x, y) d\pi(x, y) $$
左边可以分解为：
$$ \int \phi(x) \left( \int d\pi(x, y) \right) + \int \psi(y) \left( \int d\pi(x, y) \right) $$
根据 $\pi$ 的约束条件，内层积分的结果分别是边缘分布 $\mu(dx)$ 和 $\nu(dy)$。因此，左边等于：
$$ \int \phi(x) d\mu(x) + \int \psi(y) d\nu(y) $$
于是我们得到，对于任意满足 $\phi(x) + \psi(y) \leq c(x, y)$ 的势函数对 $(\phi, \psi)$ 和任意可行的运输计划 $\pi$，都有：
$$ \int \phi d\mu + \int \psi d\nu \leq \iint c d\pi $$

4. 建立并求解对偶问题

从上面的推导可以看到，$\int \phi d\mu + \int \psi d\nu$ 是原问题目标函数 $\iint c d\pi$ 的一个下界。我们自然希望找到能够尽可能大的这个下界。

因此，Kantorovich 对偶问题 被定义为：寻找一对势函数 $(\phi, \psi)$，使得它们满足约束 $\phi(x) + \psi(y) \leq c(x, y)$，并且最大化目标函数 $\int \phi d\mu + \int \psi d\nu$。

用数学语言严格地写出来就是：
$$ \sup_{\phi, \psi} \left\{ \int \phi d\mu + \int \psi d\nu : \phi(x) + \psi(y) \leq c(x, y) \ \forall x, y \right\} $$

著名的 Kantorovich 对偶定理 指出，只要成本函数 $c(x, y)$ 是“足够好”的（例如下半连续），那么对偶问题的最优值就等于原问题的最优值：
$$ \inf_{\pi \in \Pi(\mu, \nu)} \iint c d\pi = \sup_{\phi, \psi} \left\{ \int \phi d\mu + \int \psi d\nu : \phi(x) + \psi(y) \leq c(x, y) \right\} $$

这个等式意义重大。它揭示了，寻找最便宜的运输计划（原问题），等价于分配给每个源头点和目标点一个“势”（或“价格”），在满足“从 $x$ 运到 $y$ 的标价 $\phi(x) + \psi(y)$ 不能高于实际成本 $c(x, y)$”这一市场规则下，使得总收益 $\int \phi d\mu + \int \psi d\nu$ 最大。

5. 对偶形式的直观理解与优势

我们可以给对偶一个经济学的类比：想象一个拍卖市场。源头是卖家（拥有货物 $\mu$），目标地是买家（需要货物 $\nu$）。运输公司负责物流，单位成本为 $c(x, y)$。

• 卖家定价 $\phi(x)$：表示卖家 $x$ 为每单位货物设定的底价。
• 买家出价 $\psi(y)$：表示买家 $y$ 为每单位货物愿意支付的最高价。
• 约束 $\phi(x) + \psi(y) \leq c(x, y)$ 的含义是：对于任何一对可能交易的卖家 $x$ 和买家 $y$，卖家的要价加上买家的出价，不能超过把货从 $x$ 运到 $y$ 的成本。否则，这笔交易在成本上就是不可行的。
• 目标 $\int \phi d\mu + \int \psi d\nu$：是所有卖家收入与所有买家支付意愿的总和。最大化这个总和，就意味着找到了一个最有效率的资源配置和定价方案。

对偶形式的优势在于：

1. 变量转换：将优化一个复杂的联合分布 $\pi$（在函数空间）的问题，转换为优化两个普通的函数 $\phi$ 和 $\psi$，有时后者更容易处理。
2. 理论洞察：对偶函数 $\phi$ 和 $\psi$（在解存在时）满足 $c$-变换关系，即 $\psi(y) = \inf_x \{c(x, y) - \phi(x)\}$，这连接了最优传输与一类特殊的函数变换理论。
3. 算法基础：许多高效的最优传输数值算法（如基于 Sinkhorn 迭代的算法）都是直接或间接地对对偶形式进行求解或近似。
4. 推广桥梁：对偶形式更易于推广到更复杂的成本函数、正则化版本（如熵正则化）以及动态最优传输等场景。