最適輸送の双対解法 —— 相補性とC変換・変換

前章で定式化した最適輸送の双対問題を、計算機上で実際にどのように解くのかを見ていきます。 本章では、最適解において成り立つ「相補性」の条件を確認し、双対変数を片方ずつ固定しながら最適化を繰り返す「C変換」および「変換」というエレガントな反復解法の数理を導出します。

1. 相補性（Complementary Slackness）

最適輸送問題におけるラグランジュ関数を双対変数 と を用いて整理すると、次のような項が現れます。

最適解においては、輸送量に関する非負制約 と、双対問題の制約である が同時に成り立ちます。 さらに、最適化理論における**相補性の条件（Complementary Slackness）**により、これら2つの積は必ずゼロにならなければなりません。

これは、「実際に輸送が行われる（）経路においては、必ず双対制約が等号（）で成立している」という極めて重要な物理的・経済学的意味を持ちます。

2. 双対問題の再定式化

ここで、後の計算を簡明にするため、ノートの記法に沿って需要地側の双対変数の符号を反転させ、双対問題を次のように再設定します。

• 目的関数（最大化）:
• 制約条件:

目標は、この制約を満たしつつ目的関数を最大化するような と を見つけることです。

3. C変換（C-transform）

多変数の最適化を解くアプローチとして、一方の変数を固定（fix）し、もう一方の変数について最適化を行う手法を考えます。 まず、供給側の変数 を固定し、需要側の変数 について最適化を行います。

目的関数において の部分を最大化するためには、制約を満たす範囲で を可能な限り小さくする必要があります。 制約条件 を について解くと、次のようになります。

すべての に対してこの条件を満たしつつ、最も小さい を選べばよいため、次のような更新式が得られます。

この変換を C変換 と呼びます。この更新を行うことで、制約条件を満たしたまま目的関数の値は単調に増加（改善）することが保証されます。

4. 変換（C-bar transform）

次に、今度は更新された を固定（fix）し、供給側の変数 について最適化を行います。

目的関数 を最大化するためには、今度は を可能な限り大きくする必要があります。 制約条件を変形すると、以下のようになります。

すべての に対してこの条件を満たしつつ、最も大きい を選べばよいため、次のような更新式が得られます。

この変換を 変換 と呼びます。この変換後も制約 は完全に守られており、更新後の は更新前よりも大きくなる（）ため、目的関数はさらに増加します。

5. 交互最適化と収束

最適輸送の双対問題は、この「C変換」と「変換」を交互に繰り返すことで最適解へと近づいていきます。

興味深い数学的性質として、この変換を と進めると、実は となり、ある時点で更新が停止（収束）することが知られています。 このように、変数を片方ずつ固定して「上限（min）」と「下限（max）」を順に押し上げていくという極めてシンプルで強力なアルゴリズムによって、複雑な最適輸送問題の双対解を効率的に求めることができるのです。