Skip to content

定理Theorem

Kantorovich 对偶性

施工中 · 内容逐步修订

Kantorovich duality

用满足两侧势之和不超过成本的对偶函数,构造可核验的输运最优性证书。

形式陈述 ​

找到一个搬运方案以后,怎样证明再无更便宜的方案?对偶势函数为所有可行计划同时提供下界。

先取紧度量空间 X,Y、连续实成本 c 和 Borel 概率测度 μ,ν。Kantorovich 问题满足强对偶

minπ∈Π(μ,ν)∫cdπ=supφ(x)+ψ(y)≤c(x,y)(∫φdμ+∫ψdν),

其中可取连续势函数。有限分布时,右侧为 max{aTφ+bTψ:φi+ψj≤Cij}。更一般空间和成本也有对偶定理,但势的可积性、是否达到最优等条件应单独说明。

若一个可行计划 π 和一对可行势满足 φ(x)+ψ(y)=c(x,y) 在 π 几乎处处成立,则它们达到相同目标值,从而各自最优。这是互补松弛证书。

直觉

可把 φ(x)+ψ(y) 看作一条运输路线的认证成本下界。它不得超过任何真实路线成本;对任意计划平均以后,边缘约束让平均值只剩两侧势的平均,与具体计划无关。

弱对偶因此只需一行:

∫φdμ+∫ψdν=∫(φ(x)+ψ(y))dπ≤∫cdπ.

有限情形的强对偶由线性规划对偶得到;紧连续情形可通过有限划分逼近成本与测度,再用紧性和一致连续性控制误差。这一步才证明下界可以逼近最优值,不能仅凭弱对偶宣称无间隙。

证明:有限证书如何恢复为连续势 ​

下面补全紧连续情形,始终只使用本页声明的域。取两侧有限 Borel 划分 (Ai)、(Bj),每块直径不超过 δ,并在非空块内选代表 xi,yj;紧性保证这样的划分存在。令 ai=μ(Ai)、bj=ν(Bj)、Cij=c(xi,yj),记连续问题和有限问题的最优值分别为 V,Vδ。由紧空间上的一致连续性,可选 ω(δ)↓0,同时控制块内移动一个或两个坐标造成的成本变化。

任意计划按各矩形块汇总质量,得到有限可行矩阵;反过来,有限可行矩阵 P 可提升为

∑i,j:aibj>0Pijμ|Aiai⊗ν|Bjbj.

这里使用乘积测度;零质量行列的 Pij 必为零,直接略去,不作除零。提升计划有原边缘,每个块内成本与 Cij 相差至多 ω(δ)。两方向比较给出 |V−Vδ|≤ω(δ)。

有限线性规划对偶给出实向量 α,β,满足 αi+βj≤Cij 且 ∑aiαi+∑bjβj=Vδ。在整个原空间上定义

ψ(y)=mini{c(xi,y)−αi},φ(x)=miny∈Y{c(x,y)−ψ(y)}.

第一式是有限个连续函数的最小值;第二式在紧集上取最小值,且 |φ(x)−φ(x′)|≤supy|c(x,y)−c(x′,y)|,所以两势均连续并满足 φ+ψ≤c。又有 ψ(yj)≥βj;由 ψ(y)≤c(xi,y)−αi,有 φ(xi)≥αi。两势在相应划分块上的振幅各不超过 ω(δ),因而

∫φdμ+∫ψdν≥Vδ−2ω(δ)≥V−3ω(δ).

令 δ↓0,配合弱对偶即得强对偶。这构造了逼近最优值的连续可行势,不需要先假设连续对偶最优解存在,也没有将结论扩展到任意无界成本。

例子与边界

沿用源质量 a=(1/2,1/2)、目标质量 b=(1/4,3/4) 和成本

C=(1911),P=(1/41/401/2).

候选计划成本为 3。取势 φ=(0,−8)、ψ=(1,9),则四条路线的势和为

(19−71)≤C.

对偶目标为 (1/2)⋅0+(1/2)(−8)+(1/4)⋅1+(3/4)⋅9=3。每条实际使用的路线都达到等号,唯一未使用路线的势和低于成本。弱对偶已经足够把这个可行方案钉死为最优,无需再相信求解器的状态文字。

势出现负数并无问题,它们是优化证书而非实际收费。将 φ 全部加常数 k、ψ 全部减 k,可行性与目标值都不变,所以势一般不唯一。

一个可行但未达最优的计划也可以与可行势组成证书:原始成本减对偶值是对最优性误差的上界。若边缘约束尚未满足,这个差值就不是同一个原问题的合法最优性间隙,应先修复或控制可行性误差。

推论与应用

固定 φ 后,可将 ψ(y) 提升到 infx[c(x,y)−φ(x)],这称为成本变换;它自动满足所有路线约束。对距离成本,这种势约束进一步化成 Lipschitz 函数形式;对平方成本,最优势与凸函数相连,通向Brenier 定理。两者需要各自的成本结构,不能把任意势都当作凸梯度。

参考资料
关系图谱24 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系