← 戻る ライブラリ › 応用数学と計算数学 › 最適化理論 応用数学と計算数学
最適輸送 ある質量分布を別の分布へと最小コストで変形する方法を求める理論——砂山の移動から、画像・確率分布・細胞集団の比較まで。
直観 山盛りの砂を最小コストで穴に移す ある形をした大きな砂山と、まったく同じ総体積だが別の形をした地面の穴を想像してほしい。砂の一粒を距離 d d d d d d 最適輸送問題 である：総質量が等しい出発分布と目標分布が与えられたとき、一方を他方へ並べ替える最も安い方法を求める問題だ。
砂についての純粋に物理的なパズルのように聞こえるが、「あるモノの分布を最小コストで別の分布に合わせる」という同じ問いは、2つの確率分布、2枚の画像、2つの経済的需給プロファイル、あるいは2つの形状を比較するときには必ず現れる。最適輸送は、2つの分布がどれほど異なるかを正確に測り、一方を他方へどう変形すればよいかを正確に教えてくれる。
例: 最小の例：2つの砂山と2つの穴
位置 x = 0 x=0 x = 0 x = 10 x=10 x = 10 y = 1 y=1 y = 1 y = 9 y=9 y = 9 d d d d d d 0 → 1 0\to1 0 → 1 10 → 9 10\to9 10 → 9 0 → 9 0\to9 0 → 9 10 → 1 10\to1 10 → 1
解答 直接（交差しない）対応づけの費用は ∣ 0 − 1 ∣ + ∣ 10 − 9 ∣ = 1 + 1 = 2 |0-1|+|10-9|=1+1=2 ∣0 − 1∣ + ∣10 − 9∣ = 1 + 1 = 2 ∣ 0 − 9 ∣ + ∣ 10 − 1 ∣ = 9 + 9 = 18 |0-9|+|10-1|=9+9=18 ∣0 − 9∣ + ∣10 − 1∣ = 9 + 9 = 18 2 2 2 ∣ x − y ∣ |x-y| ∣ x − y ∣
この釣鐘型の標準正規分布 N ( 0 , 1 ) \mathcal N(0,1) N ( 0 , 1 ) 大学 モンジュの写像とカントロビッチの緩和 1781年、フランスの数学者であり軍事技師でもあったガスパール・モンジュは、この問題を正確に定式化した：空間 X X X μ \mu μ Y Y Y ν \nu ν x x x y y y c ( x , y ) c(x,y) c ( x , y ) μ \mu μ ν \nu ν T : X → Y T:X\to Y T : X → Y T # μ = ν T_{\#}\mu=\nu T # μ = ν A A A T # μ ( A ) = μ ( T − 1 ( A ) ) T_{\#}\mu(A) = \mu(T^{-1}(A)) T # μ ( A ) = μ ( T − 1 ( A ))
inf T : T # μ = ν ∫ X c ( x , T ( x ) ) d μ ( x ) \inf_{T:\ T_{\#}\mu = \nu} \int_X c(x, T(x))\, d\mu(x) T : T # μ = ν inf ∫ X c ( x , T ( x )) d μ ( x ) モンジュの元の定式化にはまったく解が存在しない ことがしばしばある。最も極端な例：μ = δ 0 \mu=\delta_0 μ = δ 0 ν = 1 2 δ − 1 + 1 2 δ 1 \nu=\frac12\delta_{-1}+\frac12\delta_{1} ν = 2 1 δ − 1 + 2 1 δ 1 T T T 0 0 0 ただ1つの 点 T ( 0 ) T(0) T ( 0 ) T # μ T_{\#}\mu T # μ T T T ν \nu ν
定義: 輸送計画とカップリング
μ ∈ P ( X ) \mu\in\mathcal P(X) μ ∈ P ( X ) ν ∈ P ( Y ) \nu\in\mathcal P(Y) ν ∈ P ( Y ) 輸送計画 （またはカップリング ）とは、X × Y X\times Y X × Y γ \gamma γ μ \mu μ ν \nu ν Π ( μ , ν ) = { γ ∈ P ( X × Y ) : ( π X ) # γ = μ , ( π Y ) # γ = ν } . \Pi(\mu,\nu) = \{\gamma \in \mathcal{P}(X\times Y) : (\pi_X)_{\#}\gamma = \mu,\ (\pi_Y)_{\#}\gamma = \nu\}. Π ( μ , ν ) = { γ ∈ P ( X × Y ) : ( π X ) # γ = μ , ( π Y ) # γ = ν } . γ \gamma γ x x x y y y T T T γ = ( i d , T ) # μ \gamma=(\mathrm{id},T)_{\#}\mu γ = ( id , T ) # μ γ \gamma γ μ ⊗ ν \mu\otimes\nu μ ⊗ ν Π ( μ , ν ) \Pi(\mu,\nu) Π ( μ , ν ) 決して空にならない 。
inf γ ∈ Π ( μ , ν ) ∫ X × Y c ( x , y ) d γ ( x , y ) \inf_{\gamma \in \Pi(\mu,\nu)} \int_{X \times Y} c(x,y)\, d\gamma(x,y) γ ∈ Π ( μ , ν ) inf ∫ X × Y c ( x , y ) d γ ( x , y ) X X X μ \mu μ Y Y Y ν \nu ν c c c φ ( x ) + ψ ( y ) ≤ c ( x , y ) \varphi(x) + \psi(y) \le c(x,y) φ ( x ) + ψ ( y ) ≤ c ( x , y ) カントロビッチ・ポテンシャル の組 φ : X → R \varphi:X\to\mathbb R φ : X → R ψ : Y → R \psi:Y\to\mathbb R ψ : Y → R min γ ∈ Π ( μ , ν ) ∫ X × Y c d γ = sup φ ( x ) + ψ ( y ) ≤ c ( x , y ) ( ∫ X φ d μ + ∫ Y ψ d ν ) , \min_{\gamma\in\Pi(\mu,\nu)}\int_{X\times Y} c\,d\gamma \;=\; \sup_{\varphi(x)+\psi(y)\le c(x,y)}\left(\int_X\varphi\,d\mu+\int_Y\psi\,d\nu\right), min γ ∈ Π ( μ , ν ) ∫ X × Y c d γ = sup φ ( x ) + ψ ( y ) ≤ c ( x , y ) ( ∫ X φ d μ + ∫ Y ψ d ν ) ,
なぜ正しいのか? φ ( x ) \varphi(x) φ ( x ) x x x ψ ( y ) \psi(y) ψ ( y ) y y y φ ( x ) \varphi(x) φ ( x ) ψ ( y ) \psi(y) ψ ( y ) c ( x , y ) c(x,y) c ( x , y ) φ ( x ) + ψ ( y ) ≤ c ( x , y ) \varphi(x)+\psi(y)\le c(x,y) φ ( x ) + ψ ( y ) ≤ c ( x , y ) φ ( x ) + ψ ( y ) = c ( x , y ) \varphi(x)+\psi(y)=c(x,y) φ ( x ) + ψ ( y ) = c ( x , y )
証明 有限離散測度 μ = ∑ i p i δ x i \mu=\sum_i p_i\delta_{x_i} μ = ∑ i p i δ x i ν = ∑ j q j δ y j \nu=\sum_j q_j\delta_{y_j} ν = ∑ j q j δ y j min ∑ i , j c i j γ i j \min \sum_{i,j} c_{ij}\gamma_{ij} min ∑ i , j c ij γ ij γ i j ≥ 0 \gamma_{ij}\ge0 γ ij ≥ 0 ∑ j γ i j = p i \sum_j\gamma_{ij}=p_i ∑ j γ ij = p i ∑ i γ i j = q j \sum_i\gamma_{ij}=q_j ∑ i γ ij = q j i , j i,j i , j φ i + ψ j ≤ c i j \varphi_i+\psi_j\le c_{ij} φ i + ψ j ≤ c ij max ∑ i p i φ i + ∑ j q j ψ j \max \sum_i p_i\varphi_i+\sum_j q_j\psi_j max ∑ i p i φ i + ∑ j q j ψ j p i q j p_iq_j p i q j 0 0 0 { γ i j ≥ 0 } ∩ Π ( μ , ν ) \{\gamma_{ij}\ge0\}\cap\Pi(\mu,\nu) { γ ij ≥ 0 } ∩ Π ( μ , ν ) C b ( X × Y ) C_b(X\times Y) C b ( X × Y )
上記の有限測度に対する証明は、線形計画双対性 の直接的な応用である——これはまさに凸最適化における主・双対の枠組みそのものだ：輸送計画 γ \gamma γ φ , ψ \varphi,\psi φ , ψ Π ( μ , ν ) \Pi(\mu,\nu) Π ( μ , ν ) μ , ν , γ \mu,\nu,\gamma μ , ν , γ
発展 ブレニエの定理とワッサースタイン空間の幾何 μ , ν \mu,\nu μ , ν R n \mathbb R^n R n μ \mu μ c ( x , y ) = ∣ x − y ∣ 2 c(x,y) = |x-y|^2 c ( x , y ) = ∣ x − y ∣ 2 φ : R n → R \varphi:\mathbb R^n\to\mathbb R φ : R n → R T = ∇ φ T = \nabla \varphi T = ∇ φ μ \mu μ T # μ = ν T_{\#}\mu=\nu T # μ = ν
なぜ正しいのか? ∣ x − y ∣ 2 |x-y|^2 ∣ x − y ∣ 2 c c c ( x i , y i ) (x_i,y_i) ( x i , y i ) φ \varphi φ i i i x i x_i x i y i y_i y i まさに 一致することが分かる——これは巡回単調な集合を凸関数の劣微分として特徴づけるロックアフェラーの定理である。μ \mu μ μ \mu μ T = ∇ φ T=\nabla\varphi T = ∇ φ
証明 （概略、Brenier 1991 に従う。）ステップ1：c = ∣ x − y ∣ 2 c=|x-y|^2 c = ∣ x − y ∣ 2 φ ( x ) = 1 2 ∣ x ∣ 2 − φ ~ ( x ) \varphi(x)=\tfrac12|x|^2-\tilde\varphi(x) φ ( x ) = 2 1 ∣ x ∣ 2 − φ ~ ( x ) φ \varphi φ φ ∗ ( y ) = sup x ( x ⋅ y − φ ( x ) ) \varphi^*(y)=\sup_x(x\cdot y-\varphi(x)) φ ∗ ( y ) = sup x ( x ⋅ y − φ ( x )) γ \gamma γ y ∈ ∂ φ ( x ) y\in\partial\varphi(x) y ∈ ∂ φ ( x ) R n × R n \mathbb R^n\times\mathbb R^n R n × R n φ \varphi φ ∂ φ \partial\varphi ∂ φ γ \gamma γ ∫ ∣ x − y ∣ 2 d γ \int|x-y|^2\,d\gamma ∫ ∣ x − y ∣ 2 d γ ∑ i ∣ x i − y i ∣ 2 \sum_i|x_i-y_i|^2 ∑ i ∣ x i − y i ∣ 2 μ ≪ \mu\ll μ ≪ φ \varphi φ μ \mu μ γ \gamma γ { ( x , ∇ φ ( x ) ) } \{(x,\nabla\varphi(x))\} {( x , ∇ φ ( x ))} γ = ( i d , ∇ φ ) # μ \gamma=(\mathrm{id},\nabla\varphi)_{\#}\mu γ = ( id , ∇ φ ) # μ T = ∇ φ T=\nabla\varphi T = ∇ φ μ \mu μ
コストを ∣ x − y ∣ 2 |x-y|^2 ∣ x − y ∣ 2 距離 ——2次ワッサースタイン距離 W 2 W_2 W 2 P 2 ( R n ) \mathcal P_2(\mathbb R^n) P 2 ( R n ) W 2 W_2 W 2 無限次元リーマン多様体 のようにふるまう：フェリックス・オットーによるヒューリスティック——現在ではオットー計算 と呼ばれる——は、μ \mu μ ∂ t μ + ∇ ⋅ ( μ v ) = 0 \partial_t\mu+\nabla\!\cdot(\mu v)=0 ∂ t μ + ∇ ⋅ ( μv ) = 0 v v v ⟨ v , w ⟩ μ = ∫ v ⋅ w d μ \langle v,w\rangle_\mu=\int v\cdot w\,d\mu ⟨ v , w ⟩ μ = ∫ v ⋅ w d μ T = ∇ φ T=\nabla\varphi T = ∇ φ μ t = ( ( 1 − t ) i d + t T ) # μ \mu_t=((1-t)\,\mathrm{id}+t\,T)_{\#}\mu μ t = (( 1 − t ) id + t T ) # μ
W 2 ( μ , ν ) 2 = min γ ∈ Π ( μ , ν ) ∫ ∣ x − y ∣ 2 d γ ( x , y ) W_2(\mu,\nu)^2 = \min_{\gamma \in \Pi(\mu,\nu)} \int |x-y|^2\, d\gamma(x,y) W 2 ( μ , ν ) 2 = γ ∈ Π ( μ , ν ) min ∫ ∣ x − y ∣ 2 d γ ( x , y ) 例: 中心化された2つのガウス分布間の明示的な最適輸送
μ = N ( 0 , 1 ) \mu=\mathcal N(0,1) μ = N ( 0 , 1 ) ν = N ( 0 , 2.25 ) \nu=\mathcal N(0,2.25) ν = N ( 0 , 2.25 ) σ 1 = 1 \sigma_1=1 σ 1 = 1 σ 2 = 1.5 \sigma_2=1.5 σ 2 = 1.5 μ \mu μ ν \nu ν T T T W 2 ( μ , ν ) W_2(\mu,\nu) W 2 ( μ , ν )
解答 両測度とも中心化されているので、一般的な1次元ガウス最適輸送写像 T ( x ) = m 2 + σ 2 σ 1 ( x − m 1 ) T(x) = m_2 + \frac{\sigma_2}{\sigma_1}(x - m_1) T ( x ) = m 2 + σ 1 σ 2 ( x − m 1 ) T ( x ) = σ 2 σ 1 x = 1.5 x T(x)=\frac{\sigma_2}{\sigma_1}x=1.5x T ( x ) = σ 1 σ 2 x = 1.5 x φ ( x ) = 0.75 x 2 \varphi(x)=0.75x^2 φ ( x ) = 0.75 x 2 φ ′ ( x ) = 1.5 x = T ( x ) \varphi'(x)=1.5x=T(x) φ ′ ( x ) = 1.5 x = T ( x ) T T T μ \mu μ ν \nu ν X ∼ N ( 0 , 1 ) X\sim\mathcal N(0,1) X ∼ N ( 0 , 1 ) 1.5 X ∼ N ( 0 , 1.5 2 ) = N ( 0 , 2.25 ) = ν 1.5X\sim\mathcal N(0,1.5^2)=\mathcal N(0,2.25)=\nu 1.5 X ∼ N ( 0 , 1. 5 2 ) = N ( 0 , 2.25 ) = ν ∫ ( T ( x ) − x ) 2 d μ ( x ) = ∫ ( 0.5 x ) 2 d μ ( x ) = 0.25 ⋅ V a r ( X ) = 0.25 \int(T(x)-x)^2\,d\mu(x)=\int(0.5x)^2\,d\mu(x)=0.25\cdot\mathrm{Var}(X)=0.25 ∫ ( T ( x ) − x ) 2 d μ ( x ) = ∫ ( 0.5 x ) 2 d μ ( x ) = 0.25 ⋅ Var ( X ) = 0.25 W 2 ( μ , ν ) = 0.25 = 0.5 = σ 2 − σ 1 W_2(\mu,\nu)=\sqrt{0.25}=0.5=\sigma_2-\sigma_1 W 2 ( μ , ν ) = 0.25 = 0.5 = σ 2 − σ 1
このウィジェットは本来、一般的な2次元線形写像 ( x , y ) ↦ ( a x + b y , c x + d y ) (x,y)\mapsto(ax+by,cx+dy) ( x , y ) ↦ ( a x + b y , c x + d y ) a = d = 1.5 a=d=1.5 a = d = 1.5 b = c = 0 b=c=0 b = c = 0 T ( x ) = 1.5 x T(x)=1.5x T ( x ) = 1.5 x N ( 0 , 1 ) \mathcal N(0,1) N ( 0 , 1 ) N ( 0 , 2.25 ) \mathcal N(0,2.25) N ( 0 , 2.25 ) T ( x ) = 1.5 x T(x)=1.5x T ( x ) = 1.5 x φ ( x ) = 0.75 x 2 \varphi(x)=0.75x^2 φ ( x ) = 0.75 x 2 a ≠ d a\ne d a = d b , c ≠ 0 b,c\ne0 b , c = 0 歴史的ノート
ガスパール・モンジュ （1746–1818）は、ナポレオン配下のフランス人数学者・軍事技師（エコール・ポリテクニークの創設者の一人でもある）であり、1781年の覚書『Mémoire sur la théorie des déblais et des remblais 』（「掘削と盛土の理論について」）において輸送問題を初めて提起した——文字通り、掘り出した土を最小コストで建設現場へ移す問題である。その後この問題は1世紀以上のあいだほとんど忘れ去られていた。ソビエトの数学者レオニード・カントロビッチ （1912–1986）は、ソビエトの経済計画のために線形計画法を発展させる過程で、1942年にこの問題を再発見し根本的に一般化した；輸送計画への緩和により問題は凸で扱いやすくなり、彼はこの功績と資源の最適配分に関する関連研究により、1975年のノーベル経済学賞を（チャリング・クープマンスと共同で）受賞した。ヤン・ブレニエ は1991年に勾配・極分解定理を証明し、最適輸送と凸解析、モンジュ・アンペール方程式との深い結びつきを明らかにした。セドリック・ヴィラーニ は2010年フィールズ賞を受賞したが、公式の授賞理由はボルツマン方程式に対する非線形ランダウ減衰と平衡への収束の証明を強調するものであった——これらの成果は、ヴィラーニ自身が発展させ2冊の影響力ある教科書に体系化した最適輸送理論の技法の上に築かれたものであり、この分野を現代解析学・幾何学の中心的道具として確立した。
研究 変位凸性、曲率、そして大規模輸送 ワッサースタイン空間 ( P 2 ( R n ) , W 2 ) (\mathcal P_2(\mathbb R^n),W_2) ( P 2 ( R n ) , W 2 ) μ t \mu_t μ t 変位補間 と呼ばれる；測度上の汎関数 F F F μ = ρ d x \mu=\rho\,dx μ = ρ d x ∫ ρ log ρ \int\rho\log\rho ∫ ρ log ρ t ↦ F ( μ t ) t\mapsto F(\mu_t) t ↦ F ( μ t ) 変位凸 であるという。2006年から2009年ごろ、ジョン・ロットとセドリック・ヴィラーニ 、および独立にカール゠テオドール・シュトゥルム は、W 2 W_2 W 2 C D ( K , N ) \mathrm{CD}(K,N) CD ( K , N ) 定義 した。注目すべきことに、これらの曲率-次元下界はグロモフ・ハウスドルフ極限のもとで安定であり、幾何学者たちはリーマン多様体の極限として生じる「曲がった」空間や、そもそも滑らかであったことのない空間（グラフ、フラクタル、特異空間）を理解できるようになった。
まったく異なる、きわめて現代的な応用として：2017年、マーティン・アルジョフスキー、スミス・チンタラ、レオン・ボトゥーはワッサースタインGAN を提案し、古典的な敵対的生成ネットワークの学習に使われていたイェンセン・シャノン距離を、実データ分布と生成データ分布の間のワッサースタイン1距離（カントロビッチ・ルービンシュタインの双対形式）に置き換えた。W 1 W_1 W 1
研究の最前線 2026年時点
研究の現在地（2026年時点）。
1. エントロピー正則化とシンクホーン・アルゴリズム。 カントロビッチ線形計画を厳密に解くことはスケールしない：片側 n n n O ( n 3 log n ) O(n^3\log n) O ( n 3 log n ) min γ ∈ Π ( μ , ν ) ∫ c d γ − ε H ( γ ) \min_{\gamma\in\Pi(\mu,\nu)}\int c\,d\gamma-\varepsilon H(\gamma) min γ ∈ Π ( μ , ν ) ∫ c d γ − ε H ( γ ) γ = d i a g ( u ) K d i a g ( v ) \gamma=\mathrm{diag}(u)K\mathrm{diag}(v) γ = diag ( u ) K diag ( v ) K = e − c / ε K=e^{-c/\varepsilon} K = e − c / ε シンクホーン・クノップ 行列スケーリング法で1回の反復あたり O ( n 2 ) O(n^2) O ( n 2 ) 非平衡最適輸送。 実データは両側で総質量がぴったり等しいことはまれである（例えば増殖したり死んだりする細胞集団）。非平衡最適輸送 は、厳密な周辺制約 γ ∈ Π ( μ , ν ) \gamma\in\Pi(\mu,\nu) γ ∈ Π ( μ , ν ) 単一細胞生物学と生成AI。 この非平衡かつエントロピー正則化された枠組みは、いまや計算生物学の中心にある：2025年にNature で報告されたMoscot のようなフレームワークは、非平衡・エントロピー最適輸送を用いて、時間点・空間位置・分子モダリティにまたがる数百万個の単一細胞を、細胞の誕生と死を正しく考慮しながら対応づける——単純な等質量マッチングでは誤ってしまう発生軌跡を再構築するのである。生成モデリング側では、2024〜2026年の研究が非平衡輸送とフローマッチングを組み合わせ、複雑で増減する集団のシミュレーション不要なニューラルモデルを学習させており、2017年のワッサースタインGANが開いた流れを延長している。
モンジュの元の最適輸送の定式化がときに全く解を持たない一方で、カントロビッチの緩和が（穏やかな条件のもとで）常に最小化元を持つのはなぜか。
モンジュは T # μ = ν T_{\#}\mu=\nu T # μ = ν T T T γ ∈ Π ( μ , ν ) \gamma\in\Pi(\mu,\nu) γ ∈ Π ( μ , ν ) Π ( μ , ν ) \Pi(\mu,\nu) Π ( μ , ν ) モンジュの費用関数は常に不連続であり、カントロビッチの費用関数は常に連続である。 カントロビッチは出発測度と目標測度の総質量が等しいことを要求したが、モンジュはそうしなかった。 モンジュの問題は最大化問題であり、カントロビッチの問題は最小化問題である。 ブレニエの定理によれば、二次コスト c ( x , y ) = ∣ x − y ∣ 2 c(x,y)=|x-y|^2 c ( x , y ) = ∣ x − y ∣ 2 R n \mathbb R^n R n μ \mu μ T T T
ある凸関数 φ \varphi φ T = ∇ φ T=\nabla\varphi T = ∇ φ T T T x x x μ \mu μ ν \nu ν T T T ある凹関数 ψ \psi ψ T = ψ T=\psi T = ψ カントロビッチ双対定理において、双対問題の2つのカントロビッチ・ポテンシャル φ \varphi φ ψ \psi ψ
φ ( x ) − ψ ( y ) = c ( x , y ) \varphi(x)-\psi(y)=c(x,y) φ ( x ) − ψ ( y ) = c ( x , y ) φ ( x ) + ψ ( y ) ≤ c ( x , y ) \varphi(x)+\psi(y)\le c(x,y) φ ( x ) + ψ ( y ) ≤ c ( x , y ) φ ( x ) ⋅ ψ ( y ) = c ( x , y ) \varphi(x)\cdot\psi(y)=c(x,y) φ ( x ) ⋅ ψ ( y ) = c ( x , y ) すべての x , y x,y x , y φ ( x ) = ψ ( y ) \varphi(x)=\psi(y) φ ( x ) = ψ ( y ) クトゥリの2013年エントロピー正則化（シンクホーン・アルゴリズムにつながった）は、なぜ機械学習における計算最適輸送を一変させたのか。
厳密な線形計画（ほぼ3乗のスケーリング）を、1回の反復あたり O ( n 2 ) O(n^2) O ( n 2 ) あらゆる費用関数に対して最適輸送写像が常に閉形式解を持つことを証明した。 Π ( μ , ν ) \Pi(\mu,\nu) Π ( μ , ν ) 離散測度に対してモンジュ問題とカントロビッチ問題が常に一致することを示した。