形式陈述
一个匹配中,任意两条路线交换目标都不能改进,是否足以证明最优?高维情形还要检查更多路线组成的循环。
给定成本 ,集合 称为 -循环单调,若任取有限组 ,令 ,都有
等价地可以对任意排列比较,因为排列可分解为不相交循环。左侧保留原配对,右侧只轮换目的地,因此源、目标边缘质量均未改变。
对 上的平方成本和有限二阶矩分布,输运计划理路Kantorovich 输运问题Kantorovich transport problem在指定边缘的联合分布上最小化搬运成本,允许拆分质量并利用弱紧性保证最优计划存在。最优,当且仅当它集中在一个 Borel 平方成本循环单调集合上。一般成本版本需要另外的连续性、可测性与可积性条件,本页的充分性陈述限定在上述平方成本情形。
直觉
有限离散计划中,若一组使用中的路线违反不等式,可从每条路线取同样一小份质量,循环改送,边缘不变而总成本下降。所以最优方案必须禁止所有有限循环改进。连续支撑中的严格违反可在小邻域内保持,再从这些邻域调配小份质量,得到同样矛盾。
平方成本展开后,所有 、 相互抵消,条件成为
两点情形仅要求 。所有循环都成立则更强:Rockafellar 的循环单调定理使这些点对能放进一个 proper 凸函数的次梯度图理路次梯度与次微分Subgradient · Subdifferential以全局仿射下界刻画凸函数在不可微点的支撑斜率集合。中。反向可直接核验:把 沿循环相加,函数值消去,便得到上面的内积不等式。凸势的全局支撑不等式解释了平方成本下的最优性结构;从支撑势到一般无界分布的完整充分性还须处理可测性与积分,不能只写一个形式对偶便跳过这些步骤。
证明:一般支撑扰动与平方成本的充分性
必要性。 先说明一个也供一维凸成本使用的事实:在欧氏空间中,连续实成本的有限成本最优计划,其支撑不能有严格降低成本的有限循环。若支撑点 违反循环不等式,连续性给出有界矩形邻域 ,使各原路线和交换路线上的成本仍保持严格总差。每个 ;令 ,两边缘为 。取
乘积测度理路乘积测度Product measure在乘积 σ-代数上把可测矩形的测度规定为边测度乘积的测度。构造保留两边缘,而且 ;这也处理了邻域相互重叠的情形。局部成本有界,故积分修改合法;严格成本差给出 ,矛盾。平方成本下所有可行计划均有有限成本,而支撑是满质量闭集,故得到所需的 Borel 循环单调集合。
从循环构造凸势。 现在设 集中于平方成本循环单调的非空 Borel 集 ,固定 。对任意有限链 ,,定义仿射函数
允许 ,因此 。上确界使 凸、下半连续,不取 ;把链闭合回 ,循环不等式给出 。对任意 ,把链经 再闭合回 ,得到 ,故 有限。再把 接到任意链后,取上确界即得
于是 proper,且 。这给出本页所需的 Rockafellar 构造本身,而非只引用名称。
先证明可积性,再积分。 定义凸共轭理路凸共轭与 Fenchel–Young 不等式Convex conjugate · Fenchel conjugate · Fenchel–Young inequality以线性函数的最佳配对代价定义共轭,并导出原变量与对偶变量间的基本不等式。
。两函数均为下半连续 Borel 函数,Fenchel 不等式为 ,在 上等号成立。又由 ,有 。因此
且在 上
右侧对 绝对可积,由有限二阶矩和 Cauchy–Schwarz 不等式理路Cauchy–Schwarz 不等式Cauchy–Schwarz inequality · 柯西–施瓦茨不等式内积的绝对值不超过两向量范数之积,且等号精确刻画线性相关。可知。对非负 使用推前积分的边缘公式理路推前测度Pushforward measure · Image measure · 像测度沿可测映射把源测度搬到目标空间,使目标集合的质量等于其原像的质量。,便得到 、;仿射部分也可积,所以 、。
现在才对任意竞争计划 积分 Fenchel 不等式:
两侧二阶矩固定,展开 即知 最优。这证明的是完整有限二阶矩域,不要求支撑有界,也没有把一般成本的形式势当成自动可积。
例子与边界
实线上取 ,若却有 ,则
交换目标严格降低成本,所以平方成本最优计划不能交叉。这正是一维单调配对的局部理由。
高维的两点单调性理路单调算子与极大单调性Monotone operator · Maximal monotone operator · 极大单调算子用图上的内积不等式统一凸次微分与旋转关系,并以极大性保证稳定隐式步对每个输入都有唯一解。检查仍可能漏掉循环。令 是平面逆时针旋转九十度的线性映射,对任意 都有 ,因此每一对都满足两点单调性。
选 、、,相应 、、。原配对平方成本和为 。将目标轮换成 ,成本和变为 。若三个源点各有质量 ,平均成本便从 降为 。两点全部过关,三点循环仍能改进。
循环单调性描述的是计划实际承载质量的点对,而不是任意列出的候选路线。即使某个集合满足不等式,也要先构造具有正确边缘的计划,才能谈它是否解决指定输运问题。