More than 5 years have passed since last update.

Computational Optimal Transport 精読会記録 (#7: 3.5)

Posted at 2019-04-24

背景

Kantorovich problem: $L_C(\mathbf{a,b}) = \min_{\mathrm{P}\in U(\mathbf{a, b})} \langle C, P \rangle$, $U(a, b) = \{\mathrm{P}\in \mathbb{R}_+^{n\times m}\mid \mathrm{P} \mathbb{1}_m = \mathbf{a}, \mathbf{P}^T \mathbb{1}_n = \mathbf{b} \}$
Dual problem $L_C(\mathbf{a,b}) = \max_{(\mathbf{f, g})\in R(C)} \langle \mathbf{f, a}\rangle + \langle \mathbf{g, b}\rangle$, $R(C) = \{(\mathbf{f,g})\in\mathbb{R}^n\times \mathbb{R}^m \mid \mathbf{f \oplus g} \leq C\}$
$G({\bf P})$は輸送が存在する山の間に辺をはった二部グラフ
complementary: もし${\bf P}_{i,j} > 0$ (輸送する)ならば，$C_{i,j} = {\bf f}_i + {\bf g}_j$であること
feasible: $\mathbf{f} \oplus \mathbf{g} \leq \mathbf{C}$であること (負の要素を持たないこと)

ネットワークシンプレックス法の概念を説明していく
前提その1: Prop3.3で，あるcoupling matrix $P$はfeasibleかつcomplementaryであれば最適である
前提その2: NW corner ruleによって$U(a,b)$の外点${\bf P}$を作成できる
ネットワークシンプレックス法の考え方
1. あるfeasibleな解${\bf P}$から，complementaryな${\bf f, g}$を構築できる
2. もし${\bf f, g}$がfeasibleであれば，最適解である
3. もし${\bf f, g}$がinfeasibleであるとき，$P$を修正することで現在の解を更新していき，最終的に最適な解に到達する

次に項目2.と3.に関して議論する
もし作られた$\bf f, g$がfeasibleであれば，これはProp 3.3より最適解になっているため，何もしなくていい
そこで項目3.の場合，何らかの方法で更新作業が必要になる
- 今feasibilityが達成されていない$(i,j)$があるとする
- このような$(i,j)$に対応する辺$(i,j')$をグラフ$G$に付与して考えていく

$(i,j')$を追加した結果，グラフ$G$がサイクルを持ってしまう
先に述べた通り，サイクルを持っている場合はextremalでなくなり，シンプレックス法で頂点を動きながら最適化をしていることにならなくなる（たぶん），そこでこれを解消するためにサイクルを取り除く操作によってグラフを改変する
サイクルを取り除く操作は，前回使った少し$\epsilon$を足して結果として$P_{i,j}\to 0$として辺を取り除くという手法がある（グラフが変わる）
補足: §3.4でサイクルを持たないことを証明した技法と類似
こうして新しく作成したグラフから拘束条件を伝搬させ，新しい$\bf f,g$が構築できる

(§3.5.2のまとめ)

Network simplexは説明が詳細にされているが，イマイチ不明瞭で読んでいても結論が出なかった点を書き残しておく
- アルゴリズムは止まる？（頂点を移動するアナロジーとしては，$U(a,b)$がboundedなので止まるはずだが，グラフで言われると？）
- Vertexとかfeasibleとかの関係性がよく分からない（いじった解$P$がvertexかどうかは保証されているのか？）