第7章：双対性と双対ラグランジュ法

前章までで、LASSO回帰のような微分不可能な項を含む最適化問題を解くために、近接写像やADMM（交互方向乗数法）といった強力な手法を学びました。 本章では、最適化問題を「主問題（元の問題）」から「双対問題（裏側の問題）」へと変換して解くアプローチについて学びます。関数の形を裏返す「（凸共役）」の概念から出発し、制約付き問題を効率的に解く「（双対・拡張ラグランジュ法）」へのエレガントな数理展開を解き明かします。

1. 問題の分割と制約付き問題への変換

複雑な機械学習の目的関数は、往々にしてデータへの当てはまりの良さを示す損失関数 と、モデルの複雑さを抑える正則化項 の和として書かれます。

• 例： （二乗誤差）、 （L1正則化）

このままでは と が絡み合っていて解きにくいため、ADMMの時と同様に新しい変数 を導入し、問題を分割します。

2. 凸共役（ルジャンドル変換）

最適化問題を双対問題へと変換する強力な数学的ツールが「（凸共役）」です。関数 に対して、新しい変数 を用いて次のように定義される関数 を凸共役と呼びます。

この最大値を与える は、中身を微分してゼロと置くことで見つかります。

つまり、新しい変数 は元の関数の「（勾配）」そのものを表しています。この関係を用いると、元の関数 を凸共役 を使って逆算して表現することもできます。

具体例1：L2ノルム（二乗）の凸共役

元の関数が の場合、 となるため、凸共役も同じ形になります。

具体例2：L1ノルムの凸共役

元の関数が の場合を考えます。この最大化問題は、各要素について を解くことに帰着します。 もし であれば、 を無限大に飛ばすことで値は に発散してしまいます。一方、 の範囲であれば、最大値は常に になります。 このように、特定の値の範囲に条件を課す関数を「（指示関数）」と呼び、次のように表します。

（※ を満たせば0、それ以外は を返す関数です）

3. フェンシェル（Fenchel）双対性と弱双対性

凸共役を用いると、元の最適化問題（主問題）を、変数 を用いた全く新しい問題（双対問題）に書き換えることができます。これを「（フェンシェル双対性）」と呼びます。

この関係が成り立つ背景には「（弱双対性）」という性質があります。凸共役の定義 から、常に以下の不等式が成り立ちます。

これを利用して、双対関数の値と主関数の値を足し合わせると、必ず0以上になることが証明できます。

主問題の最小値と双対問題の最小値が完全に一致するとき、強双対性が成り立つと言います。

4. 双対・拡張ラグランジュ法と近接写像

フェンシェルの双対問題に対して、さらに新しい変数 を導入して制約付き問題にします。

この問題に対して、第5章で学んだ「（拡張ラグランジュ法）」を適用します。ラグランジュ乗数を （元の主変数に対応します）、ペナルティパラメータを として拡張ラグランジュ関数を作ります。

この関数を について最小化するステップを考えると、平方完成によって見覚えのある形が現れます。

これはまさに に関する「（近接写像（Proximal Operator））」の定義そのものです！

変数 はラグランジュ乗数としての更新則に従い、次のように更新されます。

5. クリップ関数への帰着と計算の効率化

具体的に、LASSO回帰のように だった場合を考えます。 このとき、凸共役 は「範囲内に収まっていれば0、はみ出れば 」という指示関数 でした。

指示関数に対する近接写像は、はみ出した部分を強制的に境界（）に押し留める「（クリップ関数（Clip関数））」となります。

前章までの軟判定しきい値関数（Soft-thresholding）が「ゼロに向かって縮める」操作だったのに対し、双対問題の世界ではそれが「（一定値で頭打ちにする）」クリップ操作へと美しく裏返るのです。 あとは、滑らかな関数となった とクリップ関数を組み合わせ、ニュートン法などの勾配法を用いて効率的に最適化を進めることが可能になります。