背景
- 前回: Computational Optimal Transport 精読会 記録 (#4: 2.5後半-2.6)は4/3に開催，今回は4/10に開催
- 職場でCOTを読んでおり，{自己満足,復習,将来のため}などの理由で記録をしている
今回の範囲の内容
- 線形計画問題の標準形によってKantorovich問題と双対問題について議論する
アンチョコ
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\}$
§3.1 Kantorovich Linear Programs
- Kantrovichの緩和問題は行列和($\sum$のインデクスが行方向と列方向2つ）で書かれているので，本章では線形計画の標準形を考えておく（復習）
- まずは主問題を標準形に直す
- とりあえず具体的な例として$|a|=n=2, |b|=m=3$の輸送問題について標準形を例に示す
L_C({\bf a,b}) = \min_{P\in U(\bf a,b)}\sum_{i\in \{1,2\}, j\in\{1,2,3\}} C_{i,j} P_{i, j}
-
まずは行列$P$と$C$をベクトル化する: テキストの通り$(i, j) \mapsto i + n(j-1)$に移す
- $(1, 1) \mapsto 1$なので$C_{1,1} = c_1$
- $(2, 1) \mapsto 2$なので$C_{2,1} = c_2$
- $(1, 2) \mapsto 3$なので$C_{1,2} = c_3$
- という感じ．輸送量$P$も同様
-
補足: 具体的なベクトル化輸送量(交互に出てくる)
- ${\bf p} = [P_{1,1} P_{2,1} P_{1,2} P_{2,2} P_{1,3} P_{2,3}]$
次にmarginal制約を置くために行列$A$を次の形で定義
-
補足: 具体的なmarginal制約
- $P_{1,1} + P_{1,2} + P_{1,3} = a_1$
- $P_{2,1} + P_{2,2} + P_{2,3} = a_2$
- $P_{1,1} + P_{2,1} = b_1$
- $P_{1,2} + P_{2,2} = b_2$
- $P_{1,3} + P_{2,3} = b_3$
\begin{align}
A &= \begin{pmatrix}
\mathbb{1}_2^T \otimes \mathbb{I}_3 \\
\mathbb{I}_2 \otimes \mathbb{1}_3^T
\end{pmatrix}\in\mathbb{R}^{(n+m)\times nm} \\
&= \begin{pmatrix}
1 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 \\
1 & 1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 1 & 1 \\
\end{pmatrix}
\end{align}
- 行列$A$を利用すると等式制約によってmarginalが表現される
A{\bf p}=\begin{pmatrix}\bf a\\ \bf b\end{pmatrix}
このあたりは微妙に本と違うかも，演算子$\otimes$次第か
標準形で表現できるため，弱双対定理や強双対定理が利用できる（←重要）
Remark 3.2
- 弱双対定理の復習が続く（§2で一応やっているため，省略）
§3.2 C-Transform
元に戻って双対問題において，$\bf f, g$の簡単な交互最適化法(C-Transform)を考えてみる
-
$f$を固定したとき，$f$のC-Transformで得られる$g$を次で定義する
- $({\bf f^C})_i = \min_{i\in [n]} C_{i,j} - f_i$
- $f$と$g$には$C_{i,j}$を超えないという制約があり，これは制約を満たす最大の量に設定する操作に相当する
- そのため $\langle \bf f,a \rangle + \langle \bf g, b\rangle \leq \langle \bf f,a \rangle + \langle \bf f^C, b\rangle$
-
$g$を固定したとき，同様に$\bar{C}$-Transformとして次を定義する
- $({\bf g^{\bar{C}}})_i = \min_{j\in [m]} C_{i,j} - g_i$
- 同様の議論から $\langle \bf f,a \rangle + \langle \bf g, b\rangle \leq \langle \bf g^{\bar{C}},a \rangle + \langle \bf g, b\rangle$
よって$C$-Transformと$\bar{C}$-Transformによってdual problemを解けそうな気がしてくるが，残念ながらすぐに飽和して終わる（Prop 3.1）
Prop 3.1
-
$\bf f \leq f' \Rightarrow \bf f^\mathbf{C} \geq f'^\mathbf{C}$
- 定義より自明
-
$\bf f^{C\bar{C}} \geq f, \bf g^{\bar{C}C} \geq g$
- $\min$が2回出てくるところをバウンドして評価すると示される
-
$\bf f^{C\bar{C}C} = f^C$
- (1)と(2)より示される
そのため2回適用するとこれ以上改善されないベクトルに収束する
Next
- 次は3.3章を頑張っていく（しばらく線形計画の話が続く）