最优传输系列-第三篇（2.5）

最优传输系列是基于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问题里优传输的路线