最適輸送「モンジュの問題」と「カントロビッチの問題」

最適輸送問題とは？

ある砂山の形 $\mu$ を別の砂山の形 $\nu$ に移すことを考える.
砂山の移動に掛かる労力が「質量」と「始点と終点の位置」で決まっているとき, トータルの労力が最小になるような移し方はどんなものだろうか？

数学的に定式化すると

砂がありえる場所の全体を領域 $\Omega \subset \mathbb{R}^d$ として表し, 砂山の形をそれぞれ確率測度 $\mu, \nu \in P(\Omega)$ で表し, 関数 $c:\Omega\times\Omega \rightarrow [0,+\infty$ ] として単位体積を始点から終点へ輸送したときの労力を表す.

モンジュの問題

次の最小化問題を満たす $T$ を見つけ出せ;
\begin{equation}
\inf\left\{\int c(x,T(x))\,d\mu(x)\,|\, T:\Omega\rightarrow\Omega :\text{可測}, T_{\#}\mu =\nu\right\}.
\end{equation}
ここで, $T_{\#}\mu$ は
\begin{equation}
T_{\#}\mu(A) = \mu(T^{-1}(A)),\quad A\in \mathcal{B}(\Omega)
\end{equation}
で与えられる測度であり, $\mu$ の $T$ による押し出し (push forward) という.

また, この最小化問題の解 $T$ は ( $\mu$ から $\nu$ への) 最適輸送写像と呼ばれる.

カントロビッチの問題

次の最小化問題を満たす $\gamma$ を見つけ出せ;
\begin{equation}
\inf\left\{\int\int_{\Omega\times\Omega} c\,d\gamma\,|\, \gamma\in\Pi(\mu,\nu)\right\}.
\end{equation}
ここで, $\Pi(\mu,\nu)$ は
\begin{equation}
\Pi(\mu,\nu) = \left\{ \gamma\in P(\Omega\times\Omega)\,|\, (\pi_1)_{\#}\gamma = \mu, (\pi_2)_{\#}\gamma = \nu\right\}
\end{equation}
により与えられる測度の族であり, この要素を ( $\mu$ から $\nu$ への) 輸送計画と呼ぶ.
ただしここで, $\pi_1, \pi_2$ はそれぞれ $\pi_1(A\times B) = A, \pi_2(A\times B) = B$ なる射影である.

また, この最小化問題の解 $\gamma$ は ( $\mu$ から $\nu$ への) 最適輸送計画と呼ばれる.

カントロビッチの問題は割と解ける

関数 $c :X\times Y\rightarrow \mathbb{R}\cup \{+\infty\}$ が下に有界かつ下半連続であるとする.
このとき, カントロビッチの問題は解を持つ.

モンジュの問題が解けるならば, カントロビッチの問題の最適輸送計画はそれ以下のコストを持つ

輸送写像 $T$ がモンジュの問題の解とすると,
\begin{equation}
\gamma_T = (\text{id}, T)_{\#}\mu
\end{equation}
は $\gamma_T \in \Pi(\mu,\nu)$ により,
\begin{align}
\int c(x,T(x))\,d\mu(x)
&= \int\int_{\Omega\times\Omega} c(x,y)\,d\gamma_T(x,y)\\
&\ge \inf\left\{\int\int_{\Omega\times\Omega} c\,d\gamma\,|\, \gamma\in\Pi(\mu,\nu)\right\}.
\end{align}

モンジュの問題は解けないが, カントロビッチの問題は解ける場合がある

これを見るためには,
\begin{align}
\mu &= \delta_0,\\
\nu &= \dfrac{\delta_0 + \delta_1}{2},\\
c(x,y)&= |x-y|
\end{align}
の条件で, それぞれの問題を考察すればよい.
つまり, $0$ にあった砂のうちの半分を $1$ に輸送することを考える.
このとき, モンジュの問題は $T(0)$ の値がいずれであっても輸送写像が作れず, 一方でカントロビッチの問題は
\begin{equation}
\gamma(\{0\}\times \{0\}) = \gamma(\{0\}\times\{1\}) = 1/2
\end{equation}
となるようなものを取れば, これが最適輸送計画となる.