第5章：制約付き最適化とスパースモデリング —— 拡張ラグランジュ法と圧縮センシング

前章では、L1ノルムを用いたLASSO回帰によってパラメータが「ゼロにつぶされる（スパースになる）」メカニズムを学びました。 本章では、第2章で触れた「条件不足（）の連立方程式」に対して、L1ノルム最小化を適用する**「圧縮センシング」**の概念を導入します。厳密な制約条件を守りながら絶対値を含む関数を最適化するための強力な枠組みである「拡張ラグランジュ法」と、変数を分離して解く「ADMM」の数理を体系的に解き明かします。

1. 制約付き最適化問題とアプローチ

ある目的関数 を最小化したいが、同時に複数の制約条件 を厳密に満たさなければならない問題を考えます。

この問題に対する代表的な2つのアプローチを振り返ります。

罰金法（Penalty Method）

制約を破ったことに対してペナルティを科す方法です。

ペナルティ係数 を無限大に近づければ制約は満たされますが、最適化の計算が極めて不安定になる（悪条件になる）という弱点があります。

ラグランジュの未定乗数法

第2章で最小ノルム解を求める際に用いた、未定乗数 を導入する方法です。

これを と のそれぞれで偏微分して と置くことで、解析的に条件を満たす解を探ります。

2. 拡張ラグランジュ法（Augmented Lagrangian）

上記2つの手法の利点を組み合わせたのが拡張ラグランジュ法です。未定乗数法に、さらに罰金項を追加して関数 を定義します。

この手法の特徴は、パラメータ と未定乗数 を以下の手順で交互に更新していく点にあります。

1. の更新： 現在の の下で、 を について最小化し を求める。
2. の更新： 次の式で未定乗数を更新する。

この の更新式は天下り的に見えますが、 について最小化した際の極小条件 を計算すると、元のラグランジュ関数の最適性条件と一致するように巧みに設計されています。ペナルティ を無限大にしなくても、正しい制約条件へ自然に収束していく安定した手法です。

3. 圧縮センシングの定式化

この強力な最適化手法を、データ数 に対してパラメータ数 が圧倒的に多い（）連立方程式 に適用します。 第2章では、無数にある解の中から「L2ノルム（）が最小のもの」を選びました。しかしここでは、**「L1ノルム（）が最小のもの」**を選ぶ問題を考えます。

L1ノルムの等高線は、原点を中心とした「ひし形」になります。このひし形を膨らませていき、制約条件の平面 と最初にぶつかる点が最適解となります。ひし形は頂点が座標軸上にあるため、平面とぶつかる点は高い確率で座標軸上（すなわち、他の成分が完全にゼロの点）になります。

これが**圧縮センシング（Compressed Sensing）**の数理的基盤です。真の解がスパース（大部分がゼロ）であるという前提があれば、データ数 が少なくても元の情報を完全に復元できる可能性を示しています。

4. 変数を逃がすテクニックとADMMの導出

圧縮センシングの問題（L1ノルム最小化 ＋ 等式制約）を解くため、**「変数を逃がす（Variable Splitting）」**というテクニックを使用します。 新しいダミー変数 を導入し、問題を次のように等価に書き換えます。

L1ノルムの処理を に、連立方程式 の処理を にそれぞれ分離します。 この問題に対して、スケーリングされた双対変数 （）を用いた拡張ラグランジュ法を適用すると、目的関数は以下のようになります。

これを 、、 の順番で交互に最適化する手法を**ADMM（Alternating Direction Method of Multipliers：交互方向乗数法）**と呼びます。具体的な更新ステップは以下の3つです。

ステップ1： の更新（制約空間への射影）

と を固定し、連立方程式 を満たしつつ を最小化する を求めます。ラグランジュの未定乗数法を用いて解くと、次の更新式が得られます。

ステップ2： の更新（近接写像・軟判定しきい値関数）

と を固定し、L1ノルムを含む部分を最小化します。これは第4章で学んだLASSOの更新式と全く同じ形であり、軟判定しきい値関数 を用いて各成分ごとに計算できます。

ステップ3： の更新（双対変数の更新）

最後に、 と のズレを蓄積し、次のステップの補正に用いる双対変数 を更新します。

このように、一見すると解くのが困難な「L1ノルム ＋ 厳密な等式制約」という問題も、ADMMを用いることで「連立方程式を解く（擬似逆行列）」「軟判定しきい値関数を通す（ゼロにつぶす）」「ズレを更新する」という単純な3つのステップの繰り返しへと分解し、効率的に解くことが可能になります。