Kantorovich双対性

同義語:Kantorovich dualityKantorovichの双対性Kantorovichの双対定理Kantorovich duality theorem

概要

Kantorovich双対性(Kantorovich duality)とは、最適輸送の最小の費用が、値段の組 $\varphi(x)+\psi(y)\le c(x,y)$ についての $\int\varphi\,d\mu+\int\psi\,d\nu$ の上限に等しいという定理である。Polish 空間の上の確率測度 $\mu,\nu$ と、$[0,\infty]$ に値をとる下半連続な費用 $c$ について、最小値は達成され、上限は有界な Borel 関数の組に限っても同じ値になる。費用が有界で連続なら、上限は互いに $c$-変換の関係にある有界な組で達成され、最適な結合はその組で等号が成り立つ集合に載る。距離の費用では Kantorovich–Rubinstein の定理に、2 乗の費用では凸関数による Brenier の定理につながる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 最適輸送, Prokhorovの定理, 下半連続

Kantorovich 双対性(Kantorovich duality)は、最適輸送の最小の費用が、「積む値段」と「降ろす値段」の組についての最大化問題の値に等しいという定理である。$X,Y$ を Polish 空間、$\mu,\nu$ をその上の確率測度、$c\colon X\times Y\to[0,\infty]$ を下半連続な費用とすると
$$ \min_{\pi\in\Pi(\mu,\nu)}\int c\,d\pi=\sup\Bigl\{\int\varphi\,d\mu+\int\psi\,d\nu\Bigm|\varphi(x)+\psi(y)\le c(x,y)\Bigr\} $$
が成り立ち、左辺の最小値は達成される。左辺は無限次元の線形計画問題で、右辺はその双対問題である。
最適輸送 には、$X,Y$ がコンパクトで $c$ が連続な場合の Kantorovich の双対定理 が、$c$-巡回単調性による完全な証明とともにある。この記事では、コンパクト性も連続性も外した上の形(thm-kd-main)を示し、相補性の条件と、距離の費用・2 乗の費用での双対問題の形を述べる。

主問題と双対問題

$X,Y$ を Polish 空間(完備可分な距離空間)とし、$\mathcal{P}(X)$ を $X$ の上の Borel 確率測度の全体とする。$\mu\in\mathcal{P}(X)$、$\nu\in\mathcal{P}(Y)$ の 結合 とは、$X\times Y$ の上の Borel 確率測度 $\pi$ で、周辺分布が $\mu$ と $\nu$ であるものをいう。結合の全体を $\Pi(\mu,\nu)$ と書く。$X\times Y$ には距離 $d((x,y),(x',y')):=d_X(x,x')+d_Y(y,y')$ を入れる。これも Polish 空間である。

主問題・双対問題と Kantorovich ポテンシャル

$c\colon X\times Y\to(-\infty,\infty]$ を下に有界な Borel 関数とする。

  1. 主問題 の値を $P(c):=\inf_{\pi\in\Pi(\mu,\nu)}\int c\,d\pi\in(-\infty,\infty]$ とする。
  2. $\varphi\in L^1(\mu)$、$\psi\in L^1(\nu)$ の組で、すべての $(x,y)\in X\times Y$ について $\varphi(x)+\psi(y)\le c(x,y)$ を満たすものを 許容な組 といい、その全体を $\Phi_c$ と書く。$\varphi,\psi$ がともに有界な Borel 関数である許容な組の全体を $\Phi_c^{\mathrm b}$ と書く。
  3. $J(\varphi,\psi):=\int\varphi\,d\mu+\int\psi\,d\nu$ とおき、双対問題 の値を $D(c):=\sup_{\Phi_c}J$、$D_{\mathrm b}(c):=\sup_{\Phi_c^{\mathrm b}}J$ とする。
  4. $D(c)$ の上限を達成する許容な組を Kantorovich ポテンシャル の組という。

最適輸送 の定義「$c$-変換と $c$-凹関数」と同じく、$\varphi\colon X\to\mathbb{R}$ の $c$-変換を $\varphi^c(y):=\inf_x\bigl(c(x,y)-\varphi(x)\bigr)$、$\psi\colon Y\to\mathbb{R}$ の $c$-変換を $\psi^c(x):=\inf_y\bigl(c(x,y)-\psi(y)\bigr)$ と書く。$\varphi^c$ は $\varphi(x)+\psi(y)\le c(x,y)$ を満たす $\psi$ のうち最大のものである。

弱い双対性

$(\varphi,\psi)\in\Phi_c$、$\pi\in\Pi(\mu,\nu)$ なら $J(\varphi,\psi)\le\int c\,d\pi$ である。とくに $D_{\mathrm b}(c)\le D(c)\le P(c)$ である。

周辺分布で積分を書き換える

$\lvert\varphi(x)\rvert+\lvert\psi(y)\rvert$ の $\pi$ による積分は $\int\lvert\varphi\rvert\,d\mu+\int\lvert\psi\rvert\,d\nu< \infty$ なので、$\varphi(x)+\psi(y)$ は $\pi$ で積分でき、その積分は $J(\varphi,\psi)$ に等しい。$c$ は下に有界なので $\int c\,d\pi\in(-\infty,\infty]$ は定まり、$\varphi(x)+\psi(y)\le c(x,y)$ を積分して $J(\varphi,\psi)\le\int c\,d\pi$ を得る。$\pi$ について下限を、組について上限をとる。$\Phi_c^{\mathrm b}\subset\Phi_c$ から $D_{\mathrm b}\le D$ である。$\square$

双対性とは、この不等式が等式になることである。

主定理

Kantorovich 双対性

$X,Y$ を Polish 空間、$\mu\in\mathcal{P}(X)$、$\nu\in\mathcal{P}(Y)$、$c\colon X\times Y\to[0,\infty]$ を下半連続関数とする。

  1. 主問題の下限は達成される。すなわち $\int c\,d\pi=P(c)$ となる $\pi\in\Pi(\mu,\nu)$ がある。
  2. $P(c)=D(c)=D_{\mathrm b}(c)$ である(値は $[0,\infty]$ で、$\infty$ の場合も含む)。
証明の筋

最小値の存在(lem-kd-exist)、有界で連続な費用での双対性(prop-kd-bounded。台の上の鎖で値段を作る)、下からの近似(lem-kd-approx・lem-kd-limit)の順に示し、最後に組み合わせる(prf-kd-main)。

まず、費用を有界な Lipschitz 関数で下から近似する。

下半連続関数の Lipschitz 近似

$(Z,d)$ を距離空間、$c\colon Z\to[0,\infty]$ を下半連続関数とし、$k=1,2,\dots$ について
$$ c_k(z):=\inf_{w\in Z}\bigl(\min(c(w),k)+k\,d(z,w)\bigr) $$
とおく。$c_k$ は $0\le c_k\le\min(c,k)$ を満たす定数 $k$ の Lipschitz 関数で、$k$ について増加し、各点で $c_k(z)\to c(z)$ である。

近くと遠くに分ける

$w=z$ とおくと $c_k(z)\le\min(c(z),k)$ である。$c_k$ は定数 $k$ の Lipschitz 関数 $z\mapsto\min(c(w),k)+k\,d(z,w)$ の下限で、値は $[0,k]$ にあるので、定数 $k$ の Lipschitz 関数である。被積分の 2 つの項はどちらも $k$ について増加するので $c_k$ も増加する。
$z$ を固定し、$0\le a< c(z)$ とする。下半連続性から $\delta>0$ があって、$d(z,w)< \delta$ なら $c(w)>a$ である。$k\ge\max(a,a/\delta)$ とすると、$d(z,w)< \delta$ の $w$ では $\min(c(w),k)\ge a$、$d(z,w)\ge\delta$ の $w$ では $k\,d(z,w)\ge a$ なので、$c_k(z)\ge a$ である。$a$ は $c(z)$ 未満で任意なので $\lim_kc_k(z)\ge c(z)$ である($c(z)=\infty$ でも同じ)。$\square$

最適な結合の存在

thm-kd-main の仮定のもとで、$\Pi(\mu,\nu)$ は弱収束について点列コンパクトであり、$\pi\mapsto\int c\,d\pi$ は弱収束について下半連続である。とくに主問題の最小値は達成される。

緊密性と単調収束

コンパクト性。 Prokhorovの定理 の系「Polish 空間の上の 1 つの測度」により、$\varepsilon>0$ についてコンパクト集合 $K\subset X$、$L\subset Y$ で $\mu(X\setminus K)\le\varepsilon$、$\nu(Y\setminus L)\le\varepsilon$ となるものがある。$\pi\in\Pi(\mu,\nu)$ なら
$$ \pi\bigl((X\times Y)\setminus(K\times L)\bigr)\le\pi\bigl((X\setminus K)\times Y\bigr)+\pi\bigl(X\times(Y\setminus L)\bigr)\le2\varepsilon $$
で、$K\times L$ はコンパクトである。よって $\Pi(\mu,\nu)$ は緊密で、同じ定理の主定理「緊密性と相対コンパクト性」により弱収束について相対コンパクトである。$\pi_j\in\Pi(\mu,\nu)$ が $\pi$ に弱収束すれば、有界連続な $f$ について $\int f(x)\,d\pi=\lim_j\int f(x)\,d\pi_j=\int f\,d\mu$ なので第 1 周辺分布は $\mu$ で、第 2 周辺分布も同様に $\nu$ である。よって $\Pi(\mu,\nu)$ は閉じていて、点列コンパクトである。
下半連続性。 lem-kd-approx の $c_k$ は有界連続なので、$\pi\mapsto\int c_k\,d\pi$ は弱収束について連続である。単調収束定理から $\int c\,d\pi=\sup_k\int c_k\,d\pi$ で、連続関数の上限なので下半連続である。
最小値。 $\int c\,d\pi_j\to P(c)$ となる列をとり、収束する部分列の極限を $\pi$ とすると、下半連続性から $\int c\,d\pi\le P(c)$ である。$\square$

次に、有界で連続な費用について、双対の最大値を有界なポテンシャルの組で達成させる。$c$ の値が負でもよい形で述べる。

有界で連続な費用の双対性

$X,Y$ を Polish 空間、$c\colon X\times Y\to\mathbb{R}$ を有界な連続関数とし、$\|c\|:=\sup\lvert c\rvert$ とおく。このとき最適な結合 $\pi$ と、上半連続で有界な関数 $\varphi\colon X\to\mathbb{R}$、$\psi\colon Y\to\mathbb{R}$ があって、次が成り立つ。

  1. すべての $(x,y)$ で $\varphi(x)+\psi(y)\le c(x,y)$ であり、$\operatorname{supp}\pi$ の上で等号が成り立つ。
  2. $\psi=\varphi^c$、$\varphi=\psi^c$ である。
  3. $\int c\,d\pi=J(\varphi,\psi)$ である。とくに主問題の最小値は $D_{\mathrm b}(c)$ に等しく、$D_{\mathrm b}(c)$ の上限は $(\varphi,\psi)$ で達成される。
台の上の鎖で値段を作る

最適な結合と台。 $c+\|c\|\ge0$ は連続なので、lem-kd-exist により $c+\|c\|$ の、したがって $c$ の最適な結合 $\pi$ がある。$X\times Y$ は可分なので、$\pi$ の台 $\Gamma:=\operatorname{supp}\pi$ は $\pi(\Gamma)=1$ を満たす(台の補集合は $\pi$ 測度 $0$ の開集合の可算個の和で書ける)。最適輸送 の補題「最適な結合の台は $c$-巡回単調である」の証明は、$c$ の有界性と連続性と、台の点の近傍が正の測度をもつことだけを使い、コンパクト性を使わない。よって $\Gamma$ は $c$-巡回単調である。
鎖の下限。 $(\bar x,\bar y)\in\Gamma$ を固定する。$N\ge0$ と $(x_1,y_1),\dots,(x_N,y_N)\in\Gamma$ について
$$ V(x):=c(x,y_1)-c(x_1,y_1)+c(x_1,y_2)-c(x_2,y_2)+\cdots+c(x_N,\bar y)-c(\bar x,\bar y) $$
とおき($N=0$ なら $V(x)=c(x,\bar y)-c(\bar x,\bar y)$)、これらすべての下限を $\varphi_0(x)$ とする。

  • (i) $c$-巡回単調性を $(\bar x,\bar y),(x_1,y_1),\dots,(x_N,y_N)$ の巡回置換に当てると $V(\bar x)\ge0$ で、$N=0$ の鎖から $\varphi_0(\bar x)=0$ である。
  • (ii) $(\tilde x,\tilde y)\in\Gamma$ なら、$\tilde x$ での鎖の先頭に $(\tilde x,\tilde y)$ を付け加えて、すべての $x$ で $\varphi_0(x)\le c(x,\tilde y)-c(\tilde x,\tilde y)+\varphi_0(\tilde x)$ である。
  • (iii) $N=0$ の鎖から $\varphi_0\le2\|c\|$ である。$N\ge1$ の鎖は $V(x)=c(x,y_1)-c(x_1,y_1)+V'(x_1)$($V'$ は残りの鎖)と書け、$V'(x_1)\ge\varphi_0(x_1)\ge c(x_1,y_1)-c(\bar x,y_1)$((ii) で $x=\bar x$ とし (i) を使う)から $V(x)\ge-2\|c\|$ である。よって $\lvert\varphi_0\rvert\le2\|c\|$ である。
  • (iv) 各鎖の値 $V$ は $x$ の連続関数なので、その下限 $\varphi_0$ は上半連続であり、とくに Borel 関数である。

$c$-変換。 $\psi:=\varphi_0^c$ とおく。$\psi(y)\le c(\bar x,y)-\varphi_0(\bar x)\le\|c\|$、$\psi\ge-3\|c\|$ で、$y$ の連続関数の下限なので上半連続である。(ii) を $c(x,\tilde y)-\varphi_0(x)\ge c(\tilde x,\tilde y)-\varphi_0(\tilde x)$ と読み、$x$ について下限をとると $\psi(\tilde y)\ge c(\tilde x,\tilde y)-\varphi_0(\tilde x)$ なので、$\Gamma$ の上で $\varphi_0(x)+\psi(y)=c(x,y)$ である。次に $\varphi:=\psi^c$ とおく。$\varphi_0+\psi\le c$ から $\varphi\ge\varphi_0$ で、$\varphi$ も有界で上半連続であり、$\varphi+\psi\le c$ と合わせて $\Gamma$ の上で $\varphi(x)+\psi(y)=c(x,y)$ である。$\varphi\ge\varphi_0$ から $\varphi^c\le\varphi_0^c=\psi$、$\varphi+\psi\le c$ から $\psi\le\varphi^c$ なので $\varphi^c=\psi$ である。これで 1 と 2 が示された。
値の一致。 $\pi(\Gamma)=1$ なので
$$ \int c\,d\pi=\int_\Gamma\bigl(\varphi(x)+\psi(y)\bigr)\,d\pi=J(\varphi,\psi)\le D_{\mathrm b}(c)\le\int c\,d\pi $$
である(最後は lem-kd-weak)。よって等号が成り立つ。$\square$

最後に、近似した費用の最小値が元の最小値に収束することを示す。

単調な近似と最小値

thm-kd-main の仮定のもとで、$c_k$ を lem-kd-approx の近似($Z=X\times Y$)とすると、$P(c_k)$ は増加して $P(c)$ に収束する。

部分列の極限で比べる

$c_k\le c_{k+1}\le c$ なので $P(c_k)$ は増加し、極限 $\ell$ は $P(c)$ 以下である。lem-kd-exist を $c_k$ に当てて最適な結合 $\pi_k$ をとり、弱収束する部分列とその極限 $\pi\in\Pi(\mu,\nu)$ をとる。$m\le k$ なら $\int c_m\,d\pi_k\le\int c_k\,d\pi_k=P(c_k)\le\ell$ で、$c_m$ は有界連続なので部分列の極限で $\int c_m\,d\pi\le\ell$ である。$m\to\infty$ として単調収束定理から $\int c\,d\pi\le\ell$、よって $P(c)\le\ell$ である。$\square$

近似で一般の費用に移す

1 は lem-kd-exist である。2:lem-kd-approx の $c_k$ は有界連続なので、prop-kd-bounded により $P(c_k)=D_{\mathrm b}(c_k)$ である。$c_k\le c$ なので $\Phi_{c_k}^{\mathrm b}\subset\Phi_c^{\mathrm b}$ で、$D_{\mathrm b}(c_k)\le D_{\mathrm b}(c)$ である。lem-kd-limit で $k\to\infty$ とすると $P(c)\le D_{\mathrm b}(c)$ で、lem-kd-weak と合わせて $P(c)=D(c)=D_{\mathrm b}(c)$ を得る。$\square$

費用が $[0,\infty)$ に値をとる下半連続関数で $X=Y$ の場合には、双対問題の上限は有界な連続関数の組に制限しても同じ値になる(GL10 Theorem 2.2、p. 13)。thm-kd-main は上限が達成されるとは述べていない。費用が連続で下に有界であり、$a\in L^1(\mu)$、$b\in L^1(\nu)$ について $c(x,y)\le a(x)+b(y)$ を満たすときは、$\Phi_c$ の中に最大値を達成する組 $(\varphi,\varphi^c)$ があり、$\varphi$ は $c$-凹関数にとれる(AG13 Theorem 1.17、p. 13)。有界な組の中で達成されるとは限らない(下の反例の表の 2 行目)。

相補性の条件

双対問題の最大値が達成されれば、最適な結合はポテンシャルで判定できる。線形計画法の相補性条件にあたる。

相補性による最適性の判定

thm-kd-main の仮定のもとで $P(c)< \infty$ とし、$(\varphi,\psi)\in\Phi_c$ が $J(\varphi,\psi)=P(c)$ を満たすとする。$\pi\in\Pi(\mu,\nu)$ について、$\pi$ が最適であることと、$\pi$-ほとんどいたるところで $\varphi(x)+\psi(y)=c(x,y)$ であることは同値である。

非負の関数の積分

$h(x,y):=c(x,y)-\varphi(x)-\psi(y)$ は非負で、prf-kd-weak と同じく $\int h\,d\pi=\int c\,d\pi-J(\varphi,\psi)=\int c\,d\pi-P(c)$ である(右辺は $[0,\infty]$ の値)。$\pi$ が最適であることはこれが $0$ であることで、非負の関数の積分が $0$ であることは $\pi$-ほとんどいたるところで $h=0$ であることと同値である。$\square$

ポテンシャルの組が 1 つ見つかれば、最適な結合はすべて集合 $\{\varphi(x)+\psi(y)=c(x,y)\}$ に載る。この集合が写像のグラフなら、最適な結合はその写像による輸送に限られる(下の ex-kd-shift)。

距離の費用と 2 乗の費用

双対問題の組は $c$-変換で改良できる。$(\varphi,\psi)$ が許容なら $\psi\le\varphi^c$ で、$\varphi^c$ に取り替えても制約は保たれ、$\varphi^c$ が可測なら値は減らない(費用が連続なら $\varphi^c$ は連続関数の下限で上半連続なので可測である)。費用が特別な形のとき、$c$-変換の結果はよく知られた関数の類になる。

距離の費用

$(X,d)$ を距離空間、$c=d$ とする。

  1. $f\colon X\to\mathbb{R}$ が定数 $1$ の Lipschitz 関数なら $f^c=-f$ である。
  2. $\psi\colon X\to\mathbb{R}$ が有界なら、$\psi^c$ は実数値の定数 $1$ の Lipschitz 関数である。
  3. $X$ が Polish 空間なら、$\mu,\nu\in\mathcal{P}(X)$ について $P(d)=\sup\bigl\{\int f\,d\mu-\int f\,d\nu\bigm|f$ は有界で定数 $1$ の Lipschitz 関数$\bigr\}$ である。
$c$-変換が符号の反転になる

要点:許容な組 $(\varphi,\psi)$ を $(\psi^c,-\psi^c)$ に取り替えても値は減らない。

詳しい証明を開く

1:$f^c(y)=\inf_x\bigl(d(x,y)-f(x)\bigr)$ は $x=y$ で $-f(y)$ 以下で、Lipschitz 性 $f(x)\le f(y)+d(x,y)$ から各項は $-f(y)$ 以上である。

2:$\psi^c(x)=\inf_y\bigl(d(x,y)-\psi(y)\bigr)$ は $-\sup\psi$ 以上で $-\psi(x)$ 以下なので実数値で、定数 $1$ の Lipschitz 関数 $x\mapsto d(x,y)-\psi(y)$ の下限なので定数 $1$ の Lipschitz 関数である。

3:$f$ が有界で定数 $1$ の Lipschitz 関数なら、1 により $(f,-f)\in\Phi_d^{\mathrm b}$ なので右辺は $D_{\mathrm b}(d)$ 以下である。逆に $(\varphi,\psi)\in\Phi_d^{\mathrm b}$ とし、$f:=\psi^c$ とおく。2 により $f$ は定数 $1$ の Lipschitz 関数で、$-\sup\psi\le f\le-\psi$ から有界である。$\varphi\le f$ で、1 により $\psi\le f^c=-f$ なので $J(\varphi,\psi)\le\int f\,d\mu-\int f\,d\nu$ である。$d$ は連続なので thm-kd-main から $P(d)=D_{\mathrm b}(d)$ で、等式を得る。$\square$

$\mu,\nu$ が 1 次のモーメントをもつとき、$P(d)$ は 1 次の Wasserstein距離 $W_1(\mu,\nu)$ である。3 は同じ記事の定理「Kantorovich–Rubinstein の定理」($\mathcal{P}_1$ の上で、定数 $1$ の Lipschitz 関数全体の上限をとる形)を、有界な関数に限り、モーメントの仮定なしに $[0,\infty]$ の値の等式として述べたものである。

2 乗の費用と凸関数

$X=Y=\mathbb{R}^n$、$c(x,y)=\frac12\lvert x-y\rvert^2$ とし、$\varphi\colon\mathbb{R}^n\to\mathbb{R}$ とする。次は同値である。

  1. ある $\psi\colon\mathbb{R}^n\to[-\infty,\infty)$(恒等的に $-\infty$ ではない)について $\varphi(x)=\inf_y\bigl(c(x,y)-\psi(y)\bigr)$ である。
  2. $u(x):=\frac12\lvert x\rvert^2-\varphi(x)$ は凸関数である。
2 乗を展開する

要点:$\frac12\lvert x\rvert^2-\varphi$ がアフィン関数の上限として書ける。

詳しい証明を開く

$c(x,y)-\psi(y)=\frac12\lvert x\rvert^2-\bigl(x\cdot y-\frac12\lvert y\rvert^2+\psi(y)\bigr)$ なので、1 は $u(x)=\sup_y\bigl(x\cdot y-\frac12\lvert y\rvert^2+\psi(y)\bigr)$ と同じである。1 ⇒ 2:$u$ はアフィン関数の上限で、仮定から実数値なので凸である。2 ⇒ 1:実数値の凸関数 $u$ は連続で、Fenchel–Moreauの定理 により $u(x)=\sup_y\bigl(x\cdot y-u^*(y)\bigr)$($u^*$ は Legendre変換、値は $(-\infty,\infty]$)である。$\psi(y):=\frac12\lvert y\rvert^2-u^*(y)$ とおけば 1 の形になる。$\square$

したがって 2 乗の費用のポテンシャルは、2 次式から凸関数を引いたものである。$\mu,\nu$ が 2 次のモーメントをもち $\mu$ が Lebesgue 測度に絶対連続なら、最適な結合は凸関数 $u$ の勾配のグラフに載り、$\nabla u(x)=x-\nabla\varphi(x)$ が最適な輸送写像になる。これが Brenierの定理 の内容である(AG13 Theorem 1.26、p. 16。ポテンシャルと劣微分の対応は同 Proposition 1.21、p. 15)。

例

平行移動と、ポテンシャルによる一意性

$\mu$ を $[0,1]$ の一様分布、$\nu$ を $[1,2]$ の一様分布、$c(x,y)=\frac12\lvert x-y\rvert^2$ とする。
答え:$P(c)=\frac12$ で、最適な結合は平行移動 $T(x)=x+1$ による $(\mathrm{id},T)_\#\mu$ だけである。
$T_\#\mu=\nu$ なので $P(c)\le\frac12$ である。$\varphi(x):=-x$、$\psi(y):=y-\frac12$ とおくと
$$ c(x,y)-\varphi(x)-\psi(y)=\tfrac12(y-x)^2-(y-x)+\tfrac12=\tfrac12(y-x-1)^2\ge0 $$
なので $(\varphi,\psi)\in\Phi_c$ で、$J(\varphi,\psi)=-\frac12+1=\frac12$ である。lem-kd-weak から $P(c)=\frac12$ で、$(\varphi,\psi)$ は Kantorovich ポテンシャルの組である。cor-kd-slack により、最適な結合はすべて集合 $\{y=x+1\}$ に載り、第 1 周辺分布が $\mu$ なので $(\mathrm{id},T)_\#\mu$ に一致する。$u(x)=\frac12x^2-\varphi(x)=\frac12x^2+x$ は凸で、$u'(x)=x+1=T(x)$ である(prop-kd-quad)。ポテンシャルの組は定数の付け替え $(\varphi+a,\psi-a)$ の自由度をもつ。

写像で運べないときのポテンシャル

$\mu=\delta_0$、$\nu=\frac12(\delta_{-1}+\delta_1)$、$c(x,y)=\lvert x-y\rvert$($\mathbb{R}$ の上)とする。
答え:$P(c)=1$ で、$f(x)=-\min(\lvert x\rvert,1)$ が prop-kd-metric の 3 の上限を達成する。
結合は $\delta_0\otimes\nu$ だけで、費用は $\frac12\cdot1+\frac12\cdot1=1$ である。$f$ は有界で定数 $1$ の Lipschitz 関数で、$\int f\,d\mu-\int f\,d\nu=0-(-1)=1$ である。輸送写像は存在しない(最適輸送 の例「輸送写像がない例」)が、双対問題には最大値がある。

反例:仮定を外すと成り立たないこと

外した仮定例成り立たなくなる結論
thm-kd-main の、$c$ が下半連続であること$X=Y=[0,1]$、$\mu=\nu$ は一様分布、$c(x,y)=\lvert x-y\rvert$($x\ne y$)、$c(x,x)=1$1 の「主問題の下限は達成される」:$P(c)=0$ だが、どの結合も $\int c\,d\pi>0$
prop-kd-bounded の、$c$ が有界であること$X=Y=\mathbb{R}$、$\mu=\delta_0$、$\nu$ は標準正規分布、$c(x,y)=\lvert x-y\rvert^2$3 の「$D_{\mathrm b}(c)$ の上限は有界な組で達成される」:上限 $1$ を達成する有界な組はない
表の反例の確かめ

各行で、ほかの仮定は満たされていることも確かめる。

確かめを開く

1 行目:$c=\lvert x-y\rvert+\mathbf{1}_{\{x=y\}}$ は非負の Borel 関数で、対角線の点では値 $1$ が近くの値の下極限 $0$ より大きいので下半連続でない。$[0,1]$ は Polish 空間である。$0< \varepsilon< 1$ について、$T_\varepsilon(x):=x+\varepsilon$($x< 1-\varepsilon$)、$x+\varepsilon-1$($x\ge1-\varepsilon$)は一様分布を保ち、どの点も動かすので、$\pi_\varepsilon:=(\mathrm{id},T_\varepsilon)_\#\mu$ の費用は $\varepsilon(1-\varepsilon)+\varepsilon(1-\varepsilon)=2\varepsilon(1-\varepsilon)$ である。$\varepsilon\to0$ として $P(c)=0$ である。一方 $c>0$ がいたるところで成り立つので、どの確率測度 $\pi$ についても $\int c\,d\pi>0$ で、下限は達成されない。双対性 $P(c)=D_{\mathrm b}(c)=0$ はこの例でも成り立っている(組 $(0,0)$ が上限を達成する)。

2 行目:$c$ は連続で、$\mathbb{R}$ は Polish 空間である。結合は $\delta_0\otimes\nu$ だけで $P(c)=\int y^2\,d\nu=1$ である。thm-kd-main から $D_{\mathrm b}(c)=1$ である。有界な $(\varphi,\psi)\in\Phi_c^{\mathrm b}$ が $J(\varphi,\psi)=1$ を満たすとすると、cor-kd-slack により $\nu$-ほとんどいたるところで $\psi(y)=y^2-\varphi(0)$ である。$\lvert\psi\rvert\le M$ なら $\nu(y^2>M+\varphi(0))=0$ となるが、正規分布はどの区間の外にも正の確率をもつので矛盾する。可積分な組 $\varphi(0)=0$、$\psi(y)=y^2$ は $\Phi_c$ の中で上限を達成するので、$D(c)$ の最大値は存在する。

歴史と出典

Kantorovich は 1942 年の論文で双対問題を導入し、Kantorovich と Rubinstein は費用が距離の場合を詳しく調べた。巡回単調性と凸関数の劣微分の関係は Rockafellar により、$c$-巡回単調性と $c$-凹関数への一般化は Rüschendorf らにより調べられた(AG13 §1.5、pp. 22–23。原論文 Kan42)。

出典

lem-kd-exist は AG13 Theorem 1.5(p. 5)の、$c$ が下に有界な場合の存在定理にあたる。prop-kd-bounded の鎖の構成は AG13 Theorem 1.6(Rockafellar の定理、p. 7)と Theorem 1.13(pp. 9–10)の証明の方法で、最適輸送 のコンパクトな場合の証明を Polish 空間に移した。双対の等式は AG13 Theorem 1.17(p. 13)が連続で $c\le a+b$ を満たす費用について、GL10 Theorem 2.2(p. 13)が $X=Y$ で $[0,\infty)$ に値をとる下半連続な費用について述べている。AG13 Definition 1.19(p. 14)は、$c$-凹関数 $\varphi$ で $(\varphi,\varphi^c)$ が双対問題の最大を達成するものを Kantorovich ポテンシャルと呼ぶ。

関連項目

参考文献

[1]
Nathael Gozlan, Christian Léonard, Transport inequalities. A survey, Markov Processes and Related Fields 16 (2010), 635–736, 2010, arXiv 版 v1:Theorem 2.2(p. 13)
[3]
Luigi Ambrosio, Nicola Gigli, A user's guide to optimal transport, Modelling and Optimisation of Flows on Networks (B. Piccoli, M. Rascle eds.), Lecture Notes in Mathematics 2062, pp. 1–155, Springer, 2013, Theorem 1.5(p. 5)、Theorem 1.6(p. 7)、Theorem 1.13(pp. 9–10)、Theorem 1.17(p. 13)、Definition 1.19(p. 14)、Proposition 1.21(p. 15)、Theorem 1.26(p. 16)、§1.5(pp. 22–23)。番号・頁は cvgmt の著者稿による

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する