最优传输系列是基于Computational Optimal Transport开源书的读书笔记
2.5 Dual Problem
在2.3小节里,我们介绍了Kantorovich,不过Kantorovich还没有讲完–它还有着等价且至关重要的的“另一半”,在这个小节里进行介绍
Kantorovich relaxation是一个凸最小化问题,而凸优化(convex optimization)问题总是成对的。
于是,2.5给出了和Kantorovich对应的凸最大化问题:
这两个公式所说的是:找到维数分别为n和m的矢量
f
f
f和
g
g
g,使得对于每个
f
i
f_{i}
fi和
g
j
g_{j}
gj,
f
i
+
g
j
≤
C
i
,
j
f_{i}+g_{j}\leq C_{i,j}
fi+gj≤Ci,j,并且最大化
⟨
f
 
,
a
⟩
+
⟨
g
 
,
b
⟩
\langle f\,,a\rangle +\langle g\,,b\rangle
⟨f,a⟩+⟨g,b⟩,此时
⟨
f
 
,
a
⟩
+
⟨
g
 
,
b
⟩
\langle f\,,a\rangle +\langle g\,,b\rangle
⟨f,a⟩+⟨g,b⟩和对应的Kantorovich最小值相等,并且得到的
(
f
,
g
)
(f,g)
(f,g)称作"Kantorovich potentials"
如果有读者感兴趣的话,这个公式的证明在书中P23
同时,书中有着一个极为详细的比喻,用来形象地讲解(2.20),但是由于两页的比喻实在是太长,在这里就不进行解释了
Figure 2.8左图中是我们熟悉的原始(primal)Kantorovich问题,每条灰色线代表两个元素间的质量传输;右图则画出了有助于理解dual problem的一个比喻。Kantorovich potential的f矢量里每个元素都可以看作一个传送门,以每单元
f
i
f_{i}
fi的费用收走
a
i
a_{i}
ai的质量,而g矢量里的元素则收
g
j
g_{j}
gj的费用把质量放在
b
j
b_{j}
bj(注意,这里的费用和质量的“来源”是无关的),并且通过改变这两组传送费用来最大化总价格,但是要保证每两座传送门的组合不必对应的路径更贵。当然,右图中所展示的费用组合的作用和左图是一样的。
Dual problem的一个重要特性是,Kantorovich最小值解对应的传输中,如果
a
i
a_{i}
ai到
b
j
b_{j}
bj有传输流,那么dual problem里一定有
f
i
+
g
j
=
C
i
,
j
f_{i}+g_{j}=C_{i,j}
fi+gj=Ci,j
这也就是说,dual problem里所有
(
a
i
,
b
j
)
,
f
i
+
g
j
=
C
i
,
j
(a_{i},b_{j}),f_{i}+g_{j}=C_{i,j}
(ai,bj),fi+gj=Ci,j就包含了所有可能在Kantorovich问题里优传输的路线
2.6节讲了一些降低复杂度的的Kantorovich特例,对于解决具体问题有很多用处,但是对最优传输的整体理解作用并不大,感兴趣的读者可以去学习。
这里第二章对于蒙日和Kantorovich问题的介绍就告一段落了,在书中的作用是打下基本概念的地基。所以,这一章的核心内容还是需要彻底理解的,让之后的学习能够有牢靠的支持–这也是为什么这章叫做“Theoretical Foundations”。
这样一说,下一章很顺理成章地叫做“Algorithmic Foundations”,开始介绍解决这两个关键最优化问题的算法,向概念基础和实际问题的链接迈出第一步。
更多推荐
最优传输系列-第三篇(2.5)
发布评论