Computational Optimal Transport 精読会 記録 (#5: 3.1-3.2)

# 背景

- 前回: [Computational Optimal Transport 精読会 記録 (#4: 2.5後半-2.6)](https://qiita.com/takilog/items/b66cde34b4431d369b5b)は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$の輸送問題について標準形を例に示す

```math
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$
   
```math
\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が表現される

```math
A{\bf p}=\begin{pmatrix}\bf a\\ \bf b\end{pmatrix}
```

- <font color="red">このあたりは微妙に本と違うかも，演算子$\otimes$次第か</font>

- 標準形で表現できるため，弱双対定理や強双対定理が利用できる（←重要）

### 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

1. $\bf f \leq f' \Rightarrow \bf f^\mathbf{C} \geq f'^\mathbf{C}$
    - 定義より自明

2. $\bf f^{C\bar{C}} \geq f, \bf g^{\bar{C}C} \geq g$
    - $\min$が2回出てくるところをバウンドして評価すると示される

3. $\bf f^{C\bar{C}C} = f^C$
    - (1)と(2)より示される

そのため2回適用するとこれ以上改善されないベクトルに収束する

# Next

- 次は3.3章を頑張っていく（しばらく線形計画の話が続く）