形式陈述
找到一个搬运方案以后,怎样证明再无更便宜的方案?对偶势函数为所有可行计划同时提供下界。
先取紧度量空间理路紧空间Compact space每个开覆盖都能缩减为有限子覆盖的拓扑空间。 、连续实成本理路拓扑连续性Topological continuity · Continuous map目标开集的逆像始终开放,从而在不使用距离时表达映射不破坏局部邻近。 和 Borel 概率测度 。Kantorovich 问题理路Kantorovich 输运问题Kantorovich transport problem在指定边缘的联合分布上最小化搬运成本,允许拆分质量并利用弱紧性保证最优计划存在。满足强对偶
其中可取连续势函数。有限分布时,右侧为 。更一般空间和成本也有对偶定理,但势的可积性、是否达到最优等条件应单独说明。
若一个可行计划 和一对可行势满足 在 几乎处处成立,则它们达到相同目标值,从而各自最优。这是互补松弛证书。
直觉
可把 看作一条运输路线的认证成本下界。它不得超过任何真实路线成本;对任意计划平均以后,边缘约束让平均值只剩两侧势的平均,与具体计划无关。
弱对偶因此只需一行:
有限情形的强对偶由线性规划对偶理路线性规划对偶Linear programming duality · LP duality从线性约束生成对偶界,并以弱对偶、强对偶和互补松弛连接两侧最优解。得到;紧连续情形可通过有限划分逼近成本与测度,再用紧性和一致连续性控制误差。这一步才证明下界可以逼近最优值,不能仅凭弱对偶宣称无间隙。
证明:有限证书如何恢复为连续势
下面补全紧连续情形,始终只使用本页声明的域。取两侧有限 Borel 划分 、,每块直径不超过 ,并在非空块内选代表 ;紧性保证这样的划分存在。令 、、,记连续问题和有限问题的最优值分别为 。由紧空间上的一致连续性,可选 ,同时控制块内移动一个或两个坐标造成的成本变化。
任意计划按各矩形块汇总质量,得到有限可行矩阵;反过来,有限可行矩阵 可提升为
这里使用乘积测度理路乘积测度Product measure在乘积 σ-代数上把可测矩形的测度规定为边测度乘积的测度。;零质量行列的 必为零,直接略去,不作除零。提升计划有原边缘,每个块内成本与 相差至多 。两方向比较给出 。
有限线性规划对偶给出实向量 ,满足 且 。在整个原空间上定义
第一式是有限个连续函数的最小值;第二式在紧集上取最小值,且
,所以两势均连续并满足 。又有 ;由 ,有 。两势在相应划分块上的振幅各不超过 ,因而
令 ,配合弱对偶即得强对偶。这构造了逼近最优值的连续可行势,不需要先假设连续对偶最优解存在,也没有将结论扩展到任意无界成本。
例子与边界
沿用源质量 、目标质量 和成本
候选计划成本为 。取势 、,则四条路线的势和为
对偶目标为 。每条实际使用的路线都达到等号,唯一未使用路线的势和低于成本。弱对偶已经足够把这个可行方案钉死为最优,无需再相信求解器的状态文字。
势出现负数并无问题,它们是优化证书而非实际收费。将 全部加常数 、 全部减 ,可行性与目标值都不变,所以势一般不唯一。
一个可行但未达最优的计划也可以与可行势组成证书:原始成本减对偶值是对最优性误差的上界。若边缘约束尚未满足,这个差值就不是同一个原问题的合法最优性间隙,应先修复或控制可行性误差。
推论与应用
固定 后,可将 提升到 ,这称为成本变换;它自动满足所有路线约束。对距离成本,这种势约束进一步化成 Lipschitz 函数形式;对平方成本,最优势与凸函数相连,通向Brenier 定理理路Brenier 定理Brenier theorem在绝对连续源和有限二阶矩条件下,平方成本最优计划由唯一的凸梯度映射给出。。两者需要各自的成本结构,不能把任意势都当作凸梯度。
参考资料