離散カントロビッチ問題とは？
商品を 個の工場から,
個のお店に輸送することを考えます.
商品の移動に掛かる労力が「質量」と「始点と終点の距離」の積で決まっているとき, トータルの労力が最小になるような移し方はどんなものでしょうか？
数学的に定式化すると
それぞれの工場での生産量を として表し, それぞれのお店での需要量を
で表します,
行列 として単位体積を工場
からお店
へ輸送したときの距離（労力）を表します.
さらに商品全体の総重量を で正規化し,
\begin{align*}
\sum_{i}a_i = 1,\quad \sum_{j}b_j = 1.
\end{align*}
と仮定して一般性を失いません*1.
数理計画問題としての定式化
離散カントロビッチ問題は, 以下の最小化問題により定式化されます*2:
\begin{equation}\tag{P}\label{P}
\mathop{\rm minimize}_{P\in H} \langle C,P \rangle
\end{equation}
ここで, 実行可能領域 は
\begin{align*}
H &= H_1 \cap H_2 \cap H_3,\\
H_1 &= \left\{p \in \mathbb{R}^{n\times m} \, |\, p_{ij} \ge 0\right\},\\
H_2 &= \left\{p \in \mathbb{R}^{n\times m} \, |\, P 1_m = a \right\},\\
H_3 &= \left\{p \in \mathbb{R}^{n\times m} \, |\, P^T1_n = b\right\}.
\end{align*}
により記述されます.
- 1つ目の条件は輸送量はマイナス値を取らないこと,
- 2つ目の条件はそれぞれの輸送元
について, 送り出した商品の総量が
であること,
- 3つ目の条件はそれぞれの輸送先
について, 受けとった商品の総量が
であること
をそれぞれ表します.
を等式制約と見なすと,
対応する Lagrange 関数 を,
\begin{equation}
L(P,f,g)
= \langle{C},{P}\rangle - \langle{f},{P1_m -a}\rangle - \langle{g},{P^T1_n- b}\rangle
\end{equation}
と定めることにより, 問題 (\ref{P}) を
\begin{align}\tag{P}
\mathop{\rm minimize}_{P\in H_1} \max_{(f,g)\in \mathbb{R}^n\times \mathbb{R}^m}L(P,f,g)
\end{align}
と書き直すことができます.
以後は最小化問題と呼んだときには, こちらの表現を念頭に置いて考察しましょう.
したがってその双対問題は, min と max をひっくり返して計算することにより,
\begin{align}\tag{Q}\label{Q}
&\mathop{\rm maximize}_{(f,g)\in \mathbb{R}^n\times \mathbb{R}^m}
\min_{P\in H_1}L(P,f,g)\\
&\quad = \mathop{\rm maximize}_{(f,g)\in \mathbb{R}^n\times \mathbb{R}^m} \left\{
\langle{f},{a}\rangle +\langle{g},{b}\rangle -\min_{P\in H_1} \langle{C-f1_m^T-1_ng^T},{P}\rangle\right\}\\
&\quad = \mathop{\rm maximize}_{(f,g)\in R(C)} \left\{
\langle{f},{a}\rangle +\langle{g},{b}\rangle\right\}, \quad R(C) = \left\{(f,g)\in \mathbb{R}^n\times \mathbb{R}^m| f_i + g_j \le C_{ij} \right\}
\end{align}
となる制約条件付き最大化問題として表すことができることが, 数理最適化の一般論からわかります.
エントロピー正則化
エントロピー関数を
\begin{equation}
H(P) = -\sum_{i,j} p_{ij}\left(\log{(p_{ij})}-1\right)
\end{equation}
により定義します*3.
さらにパラメータ を固定します.
最小化問題 \ref{P} におけるコスト関数にエントロピー関数 を加えて,
\begin{equation}\tag{P$_\varepsilon$}\label{P_eps}
\mathop{\rm minimize}_{P\in H'} \left\{\langle{C},{P}\rangle -\varepsilon H(P)\right\}
\end{equation}
により最小化問題を緩和することをエントロピー正則化と呼びます*4.
このとき, で, 不等号制約
は自動的に外せます.
なぜならば のとき,
より
であり, 最小化問題の解の候補になりえないからです.
対応する Lagrange 関数 は,
\begin{equation}
\mathcal{E}(P,f,g)
= \langle{C},{P}\rangle - \varepsilon H(P)- \langle{f},{P1_m -a}\rangle - \langle{g},{P^T1_n- b}\rangle
\end{equation}
なので, 双対問題は
\begin{align}\tag{Q$_\varepsilon$}\label{Q_eps}
&\mathop{\rm maximize}_{(f,g)\in \mathbb{R}^n\times \mathbb{R}^m}
\min_{P\in \mathbb{R}^{n\times m}}\mathcal{E}(P,f,g)\\
&\quad = \mathop{\rm maximize}_{(f,g)\in \mathbb{R}^n\times\mathbb{R}^m} \left\{
\langle{f},{a}\rangle +\langle{g},{b}\rangle - \varepsilon\langle{\exp{(f/\varepsilon)}},{K\exp{(g/\varepsilon)}}\rangle\right\}
\end{align}
であり, こちらは制約条件のない最大化問題となっています.
ただしここで, であり, 式変形には停留条件:
\begin{align*}
&\dfrac{\partial \mathcal{E}(P,f,g)}{\partial P_{ij}} = C_{ij} +\varepsilon \log(P_{ij}) -f_i -g_j = 0\\
&\Leftrightarrow P_{ij} = \exp{\left(\frac{f_i+g_j - C_{ij}}{\varepsilon}\right)}
\end{align*}
を用いました.
エントロピー関数の形状が凸であり, また境界近傍の傾きが により発散していることから, 微分により停留条件を求めることができています.
以上をまとめると,
- 問題 (\ref{P}) ... affine なので, 最適値は頂点に存在し, 一意とは限らない
- 問題 (\ref{Q}) ... 線形計画法の双対問題なので双対ギャップは現れないが, 制約条件が残る
- 問題 (\ref{P_eps}) ... strictly convex なので最適値は一意に存在し, エントロピー関数のおかげで最適値は内部に存在する
- 問題 (\ref{Q_eps}) ... strictly convex の双対問題なので双対ギャップは現れず, 制約条件もない
ことがわかります.
さらに, 問題 (\ref{P}) は最大流問題に帰着させることができ, 問題 (\ref{P_eps}), (\ref{Q_eps}) はSinkhorn のアルゴリズムによって効率よく近似解を求めることができることが知られています.
