Skip to content

定义Definition

输运的循环单调性

施工中 · 内容逐步修订

Cyclical monotonicity in transport

以任意有限循环交换都不能降低成本,刻画输运支撑的最优性结构。

形式陈述 ​

一个匹配中,任意两条路线交换目标都不能改进,是否足以证明最优?高维情形还要检查更多路线组成的循环。

给定成本 c:X×Y→R,集合 Γ⊂X×Y 称为 c-循环单调,若任取有限组 (x1,y1),…,(xm,ym)∈Γ,令 ym+1=y1,都有

∑i=1mc(xi,yi)≤∑i=1mc(xi,yi+1).

等价地可以对任意排列比较,因为排列可分解为不相交循环。左侧保留原配对,右侧只轮换目的地,因此源、目标边缘质量均未改变。

对 Rd 上的平方成本和有限二阶矩分布,输运计划最优,当且仅当它集中在一个 Borel 平方成本循环单调集合上。一般成本版本需要另外的连续性、可测性与可积性条件,本页的充分性陈述限定在上述平方成本情形。

直觉

有限离散计划中,若一组使用中的路线违反不等式,可从每条路线取同样一小份质量,循环改送,边缘不变而总成本下降。所以最优方案必须禁止所有有限循环改进。连续支撑中的严格违反可在小邻域内保持,再从这些邻域调配小份质量,得到同样矛盾。

平方成本展开后,所有 |xi|2、|yi|2 相互抵消,条件成为

∑i⟨xi,yi⟩≥∑i⟨xi,yi+1⟩.

两点情形仅要求 ⟨x1−x2,y1−y2⟩≥0。所有循环都成立则更强:Rockafellar 的循环单调定理使这些点对能放进一个 proper 凸函数的次梯度图中。反向可直接核验:把 ϕ(xi−1)≥ϕ(xi)+⟨yi,xi−1−xi⟩ 沿循环相加,函数值消去,便得到上面的内积不等式。凸势的全局支撑不等式解释了平方成本下的最优性结构;从支撑势到一般无界分布的完整充分性还须处理可测性与积分,不能只写一个形式对偶便跳过这些步骤。

证明:一般支撑扰动与平方成本的充分性 ​

必要性。 先说明一个也供一维凸成本使用的事实:在欧氏空间中,连续实成本的有限成本最优计划,其支撑不能有严格降低成本的有限循环。若支撑点 (xi,yi) 违反循环不等式,连续性给出有界矩形邻域 Ui,使各原路线和交换路线上的成本仍保持严格总差。每个 π(Ui)>0;令 γi=π|Ui/π(Ui),两边缘为 μi,νi。取

0<ε≤1mminiπ(Ui),π~=π−ε∑iγi+ε∑iμi⊗νi+1.

乘积测度构造保留两边缘,而且 ε∑iγi≤π;这也处理了邻域相互重叠的情形。局部成本有界,故积分修改合法;严格成本差给出 ∫cdπ~<∫cdπ,矛盾。平方成本下所有可行计划均有有限成本,而支撑是满质量闭集,故得到所需的 Borel 循环单调集合。

从循环构造凸势。 现在设 π 集中于平方成本循环单调的非空 Borel 集 Γ,固定 (x0,y0)∈Γ。对任意有限链 (xi,yi)∈Γ,i=0,…,n,定义仿射函数

L(x)=∑i=0n−1⟨yi,xi+1−xi⟩+⟨yn,x−xn⟩,ϕ(x)=supn,链L(x).

允许 n=0,因此 ϕ(x)≥⟨y0,x−x0⟩。上确界使 ϕ 凸、下半连续,不取 −∞;把链闭合回 x0,循环不等式给出 ϕ(x0)=0。对任意 (x,y)∈Γ,把链经 x 再闭合回 x0,得到 L(x)≤⟨y,x−x0⟩,故 ϕ(x) 有限。再把 (x,y) 接到任意链后,取上确界即得

ϕ(z)≥ϕ(x)+⟨y,z−x⟩.

于是 ϕ proper,且 Γ⊂graph(∂ϕ)。这给出本页所需的 Rockafellar 构造本身,而非只引用名称。

先证明可积性,再积分。 定义凸共轭 ϕ∗(y)=supx{⟨x,y⟩−ϕ(x)}。两函数均为下半连续 Borel 函数,Fenchel 不等式为 ϕ(x)+ϕ∗(y)≥⟨x,y⟩,在 Γ 上等号成立。又由 ϕ(x0)=0,有 ϕ∗(y)≥⟨x0,y⟩。因此

f(x)=ϕ(x)−⟨y0,x−x0⟩≥0,g(y)=ϕ∗(y)−⟨x0,y⟩≥0,

且在 Γ 上

f(x)+g(y)=⟨x−x0,y−y0⟩.

右侧对 π 绝对可积,由有限二阶矩和 Cauchy–Schwarz 不等式可知。对非负 f,g 使用推前积分的边缘公式,便得到 f∈L1(μ)、g∈L1(ν);仿射部分也可积,所以 ϕ∈L1(μ)、ϕ∗∈L1(ν)。

现在才对任意竞争计划 π~ 积分 Fenchel 不等式:

∫⟨x,y⟩dπ~≤∫ϕdμ+∫ϕ∗dν=∫⟨x,y⟩dπ.

两侧二阶矩固定,展开 |x−y|2 即知 π 最优。这证明的是完整有限二阶矩域,不要求支撑有界,也没有把一般成本的形式势当成自动可积。

例子与边界

实线上取 x1<x2,若却有 y1>y2,则

|x1−y1|2+|x2−y2|2−|x1−y2|2−|x2−y1|2=2(x2−x1)(y1−y2)>0.

交换目标严格降低成本,所以平方成本最优计划不能交叉。这正是一维单调配对的局部理由。

高维的两点单调性检查仍可能漏掉循环。令 J 是平面逆时针旋转九十度的线性映射,对任意 x,x′ 都有 ⟨x−x′,Jx−Jx′⟩=0,因此每一对都满足两点单调性。

选 x1=(0,0)、x2=(0,1)、x3=(1,0),相应 y1=(0,0)、y2=(−1,0)、y3=(0,1)。原配对平方成本和为 0+2+2=4。将目标轮换成 (y2,y3,y1),成本和变为 1+0+1=2。若三个源点各有质量 1/3,平均成本便从 4/3 降为 2/3。两点全部过关,三点循环仍能改进。

循环单调性描述的是计划实际承载质量的点对,而不是任意列出的候选路线。即使某个集合满足不等式,也要先构造具有正确边缘的计划,才能谈它是否解决指定输运问题。

推论与应用

在紧空间、连续成本的Kantorovich 对偶版本中,势函数达到等号的集合自动满足循环不等式:沿循环把势相加,源势与目标势总和不变。反方向在平方成本下导向凸势,再结合源分布绝对连续,得到Brenier 最优映射。它把有限循环的可改进性连接到连续空间中的梯度结构。

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

拖动节点调整位置。

显示关系

显示:依赖

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