最適輸送と双対問題 —— ラグランジュ緩和とコスト最小化

これまでの章では、主に機械学習における「モデルの予測誤差の最小化」を扱ってきました。 本章からは視点を変え、ある分布から別の分布へ「モノやデータを移動させる」際のコストを最小化する**最適輸送問題（Optimal Transport Problem）**を考えます。この問題を通して、制約付き最適化の難しさを突破する「ラグランジュ緩和」と、全く別の視点から同じ最適解を導き出す「双対問題」の美しい数理を解き明かします。

1. 最適輸送問題の定式化

番目の供給地から の物資が出発し、 番目の需要地に の物資を届ける状況を考えます。 供給地 から需要地 へ物資を 単位運ぶための移動コストを とし、実際に運ぶ量（輸送プラン）を とします。

目標は、全体の総輸送コストを最小化する輸送プラン を見つけることです。これは以下の最適化問題として定式化されます。

• 目的関数:
• 制約条件: * 供給の制約： （各 から出る総量は に等しい）
  • 需要の制約： （各 に入る総量は に等しい）
  • 非負制約： （負の量は運べない）

2. 制約付き最適化と指示関数

一般的な制約付き最適化問題は、等式制約 と不等式制約 を持ちます。

これを「制約なし」の最適化問題の形に無理やり書き換えるため、条件を満たさない場合に無限大のペナルティを与える指示関数 と を導入します。

• は、 なら 、 なら を返す関数。
• は、 なら 、 なら を返す関数。

これらを用いると、元の問題は次のように書き換えられます。

しかし、指示関数は に跳ね上がる「壁」のような関数であり、微分ができないため数学的に扱いづらいという問題があります。

3. ラグランジュ緩和（下界による代理）

そこで、指示関数の無限大の壁を、傾き を持つ「直線（一次関数）」で下から支える（代理する）ことを考えます。これがラグランジュ緩和です。

指示関数を一次関数 に置き換えた関数をラグランジュ関数 と呼びます。

このラグランジュ関数を について最小化したものを、双対関数 と定義します。

直線は常に指示関数の下側にある（下界となる）ため、この双対関数 を について**最大化（突き上げる）**することで、元の問題の最小値に下から迫ることができるのです。

4. 最適輸送問題の双対問題

このラグランジュ緩和の手法を、実際の最適輸送問題に適用してみましょう。 非負制約 はそのまま残し、供給と需要の等式制約に対して未定乗数 を導入してラグランジュ関数を作ります。

これを でくくり直して整理します。

双対関数 は、この を の条件下で最小化したものです。 もし係数 が負になるような のペアが一つでも存在すれば、 とすることで最小値は に発散してしまいます。 これを防ぐためには、すべての において以下の条件を満たす必要があります。

この条件が満たされているとき、 に依存する項の最小値は となり、双対問題は以下のようになります。

• 目的関数:
• 制約条件:

最適輸送問題のような線形計画問題においては、強双対定理が成り立ちます。すなわち、元の問題（主問題）の最小コストと、この双対問題の最大値は完全に一致します。

5. 双対変数の経済学的解釈

導出された双対問題は、極めて興味深い経済学的な解釈を持っています。 双対変数 を、それぞれの地点における物資の「潜在価格（限界費用）」だと考えてみましょう。

• : 供給地 における物資の価値（処分コスト）
• : 需要地 における物資の価値（販売価格）
• : 「供給地と需要地の価格差（利益）は、輸送コスト を上回ることはできない」という市場の裁定条件を表しています。

最適輸送問題は、「総輸送コストをいかに最小にするか」という物理的なパズルでしたが、双対問題に変換することで「輸送業者の利益がコストを上回らない範囲で、各拠点の潜在価値をいかに最大化するか」という価格決定のパズルへと鮮やかに姿を変えるのです。