Computational Optimal Transport 精読会 記録 (#3: 2.5前半)

背景

• 前回: Computational Optimal Transport 精読会 記録 (#2: 2.4)は3/18に開催，今回は3/25に開催
• 職場でCOTを読んでおり，{自己満足,復習,将来のため}などの理由で記録をしている

今回の範囲の内容

• Kantorovich問題の双対問題について(後半)と残りの諸定理について(測度論パートは含まない)

アンチョコ

• coupling matrix: $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} \}$

• Kantorovich problem: $L_C(\mathbf{a,b}) = \min_{\mathrm{P}\in U(\mathbf{a, b})} \langle C, P \rangle$

2.5 Dual Problem

• Prop2.4ではKantorovich problemの双対問題としての特徴を見ていく

Prop 2.4

• 主張
  • $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\}$ (注) 本では$\forall (i,j)$がある
• $\mathbf{f, g}$をKantorovich potentialと呼ぶ

Prop 2.4の解説(Proof)

• Lagrangian dualityから以下を議論する

  • 参考資料: http://www.eng.newcastle.edu.au/eecs/cdsc/books/cce/Slides/Duality.pdf
  • infを取った関数をmaxする操作を参考にする

• 以下のように最適化問題を変形する

  • (注イメージのみ): max (f, g)を挟むと，この項を0にして最小化するには，coupling matrixの制約条件を満たす必要がある（上げて落とす）
  • $f\oplus g = f 1_m^T + 1_n g^T$ の部分を計算するには，簡単な方法では要素ごとに分解して計算すると一致すると分かる

\begin{align}
& \min_{P\geq 0} \max_{(f,g)\in R^n\times R^n} \langle C, P\rangle + \langle a - P 1_m\rangle + \langle b - P^T 1_n, g\rangle \\
& = \max_{(f,g)\in R^n\times R^m} \langle a, f\rangle + \langle b, g\rangle + \min_{P\geq 0} \langle C - f 1_m^T - 1_n g^T, P\rangle 
\end{align}

• $P$に関する部分について以下が成り立つので

\min_{P\geq 0} \langle Q, P\rangle = \begin{cases}
0 & \text{if} Q \geq 0\\
-\infty &\text{o/w}
\end{cases}

• 次の制約条件を満たさなければ最適化問題が意味のないものになる: $\mathbf{f \oplus g} \leq C$
• これはドメイン $R(C)$の条件にほかならない

次回

• 2.5の後半と応用例を読み解く