ラグランジュ乗数法の完全ガイド：制約付き最適化の理論・KKT条件とIT・機械学習への応用
エバープレイ編集部はじめに：ラグランジュ乗数法とは何か
ラグランジュ乗数法（Lagrange multipliers）は、ある制約条件のもとで目的関数を最適化（最大化または最小化）するための古典的な手法です。連続的で微分可能な関数に対して、等式制約（g(x)=0 の形）を持つ最適化問題を解析的に扱う際に非常に有効です。ITや機械学習の分野では、サポートベクターマシン（SVM）の双対問題や、制約付き最小二乗、ラグランジュ緩和（Lagrangian relaxation）、ADMM など多くのアルゴリズムの理論的基盤になっています。
基本概念と直感
最も単純な形は次の等式制約付き最適化問題です。
目的： f(x) を最大化（または最小化）
制約： g(x) = 0
ラグランジュ乗数法では、ラグランジアン L(x, λ) を導入して問題を同時に扱います。形式は書き方により符号が異なりますが、代表的には
L(x, λ) = f(x) + λ g(x)
と定義します（λ はラグランジュ乗数）。最適解では、f の勾配 ∇f は制約 g の勾配 ∇g と平行になります。直感的には、制約面上で動くときに増減がゼロになる方向（制約の接線方向）に沿っては f の変化がないので、f の勾配は接線方向に直交し、つまり g の勾配のスケール倍になります。
数学的導出（等式制約の場合）
具体的に n 次元変数 x ∈ R^n として、等式制約が m 個ある場合を考えます。各制約を c_i(x)=0（i=1,...,m）とし、ラグランジアンを
L(x, λ) = f(x) + Σ_{i=1}^m λ_i c_i(x)
と定義します。必要条件（一次条件）は次の方程式系です。
- stationarity（停留条件）: ∇_x L(x, λ) = ∇f(x) + Σ λ_i ∇c_i(x) = 0
- primal feasibility（実行可能性）: c_i(x) = 0 （全ての i）
これらを同時に解くことで候補解（局所最適解の可能性）を得ます。一般に、これらは非線形方程式系なので解析解が得られない場合は数値解法を用います。
幾何学的な説明
2次元での直感的な理解：制約 g(x,y)=0 が平面上の曲線を定めるとき、曲線上の点で f を最大化するには、その点での曲線の接線方向に沿った f の変化が 0 でなければなりません。つまり ∇f は接線方向に直交し、曲線の法線（＝∇g）方向と一致する。これが「∇f = −λ ∇g」または「∇f = α ∇g」の関係です（符号はラグランジアンの定義次第）。
具体例：単純な問題を解いてみる
例 1（円周上で xy を最大化）
問題： f(x,y)=xy、制約：x^2 + y^2 = 1
ラグランジアン：L = xy − λ(x^2+y^2−1)
偏微分条件：
- ∂L/∂x = y − 2λ x = 0 → y = 2λ x
- ∂L/∂y = x − 2λ y = 0 → x = 2λ y
- 制約：x^2 + y^2 = 1
これらを解くと、最大値は (x,y)=(1/√2,1/√2) および (−1/√2,−1/√2) で f=1/2、最小値は (1/√2,−1/√2) 等で f=−1/2、さらに x=0 などの臨界点（f=0）も得られます。
例 2（直線制約の二乗和最小化）
問題： minimize x1^2 + x2^2 subject to x1 + x2 = 1
ラグランジアン：L = x1^2 + x2^2 + λ(x1 + x2 − 1)
∂L/∂x1 = 2x1 + λ = 0、∂L/∂x2 = 2x2 + λ = 0、制約より x1 = x2 = 1/2 が得られます。
複数の制約・不等式制約とKKT条件
等式制約が複数ある場合は上で示したベクトル λ を導入します。不等式制約（g_i(x) ≤ 0）の場合は、カルッシュ—クーン—タッカー（KKT）条件が拡張された必要条件になります。主な要素は次のとおりです。
- stationarity: ∇f(x) + Σ λ_i ∇g_i(x) + Σ μ_j ∇h_j(x) = 0（等式 h_j、非等式 g_i の混在を想定）
- primal feasibility: g_i(x) ≤ 0, h_j(x)=0
- dual feasibility: λ_i ≥ 0（不等式制約に対応する乗数）
- complementary slackness: λ_i g_i(x) = 0（活性制約だけが正の乗数を持つ）
ただし、KKT 条件は「適切な制約資格（constraint qualification）」が満たされる場合に有効な必要条件です。代表的な制約資格には LICQ（線形独立性制約資格）などがあります。
二次条件（十分条件）・特異ケース
一次条件（ラグランジアンの停留条件）は必要条件に過ぎません。局所最小・最大であるためには二次条件の確認が必要です。等式制約付きの場合、ラグランジアンのヘッセ行列を制約の接空間（tangent space）に制限したときの正定性（最小化）や負定性（最大化）を調べます。
また、∇c_i が線形従属であるなど制約の特異なケースでは、標準的なラグランジュ理論が崩れることがあり、別の手法や拡張的な理論が必要です。
実務的／数値的な解法とアルゴリズム
解析的に解けない場合は数値手法を用います。代表的なアプローチ：
- 非線形方程式系としてニュートン法や準ニュートン法で同時に x と λ を求める。
- ペナルティ法：制約を目的関数に重み付きで足す（例：f(x)+ρ‖g(x)‖^2）。簡単だが大きな ρ が必要だと数値不安定。
- 拡張ラグランジアン法（augmented Lagrangian）：ラグランジアンにペナルティ項を加え、λ を反復で更新する。非線形最適化で堅牢。
- 内部点法（interior-point）：不等式制約を内部から扱い、KKT 系を数値的に解く。大規模問題に強い。
- ADMM（Alternating Direction Method of Multipliers）：問題を分解して逐次最適化＋ラグランジアン更新を行う。分散最適化に有用。
実装の注意点：
- スケーリング：目的関数・制約のスケールが異なると収束が悪くなる。
- 初期値：非線形問題では初期値に依存し局所解に陥る可能性がある。
- 数値の不安定性：ヘッセ行列の特異性やペナルティパラメータの設定に注意。
IT・機械学習における応用例
- SVM の双対問題：支持ベクトルマシンの学習はラグランジュ乗数と KKT 条件に基づく双対最適化問題として導出されます。
- 正則化とラグランジアン：等式制約として扱うことにより、正則化項が制約のラグランジアン解釈を持つことがあります（例：ある制約を厳密に満たす代わりにラグランジアンでトレードオフする視点）。
- リソース配分・スケジューリング：帯域幅や計算リソースの割当問題で効率的に最適解を求める手法として利用。
- 組合せ最適化のラグランジュ緩和：難しい整数計画を連続化してラグランジアンで緩和し、双対ギャップを使って下界を得る。
- 分散最適化：ADMM や分散ラグランジアン法はクラスタやエッジでの共同学習に使われます。
実装の簡単な疑似コード（拡張ラグランジアン法のイメージ）
拡張ラグランジアンの基本反復は次のような形です（等式制約 c(x)=0 を仮定）。
- 初期化: x^0, λ^0, ρ>0
- 反復 k=0,1,...:
- 1) x^{k+1} = argmin_x { f(x) + λ^k^T c(x) + (ρ/2) ||c(x)||^2 }
- 2) λ^{k+1} = λ^k + ρ c(x^{k+1})
実際はステップ 1 の内部最適化に数値最適化手法（準ニュートン法など）を使います。
よくある誤解と注意点
- ラグランジュ乗数法は「必ず」最適解を与えるわけではない：一次条件は必要条件であり、十分条件の確認が必要。
- 不等式制約を単にラグランジアンに足せばよいという単純化は誤りで、補完スラックネスや双対可行性など KKT の要件が重要。
- 乗数 λ の符号や定義は論文や教科書によって異なる。式や条件を書くときは符号規約を明確に。
まとめ
ラグランジュ乗数法は、等式および不等式制約付き最適化の理論と実装で中心的な役割を果たす強力な道具です。幾何学的には「目的関数の勾配が制約の勾配の線形結合になる」ことを示し、KKT 条件により不等式制約まで拡張されます。IT 分野では SVM、ADMM、ラグランジアン緩和など多彩な応用があり、理論的理解は実務でのアルゴリズム選択やチューニングに不可欠です。実装する際は数値安定性、スケーリング、初期値依存性、制約資格の問題などに注意してください。
参考文献
- Lagrange multiplier — Wikipedia
- MIT OpenCourseWare: Introduction to Mathematical Programming — Lecture Notes
- Stephen Boyd & Lieven Vandenberghe, Convex Optimization (book)
- Karush–Kuhn–Tucker conditions — Wikipedia
- J. Nocedal and S. Wright, Numerical Optimization (参考テキスト)
投稿者プロフィール
