ラグランジュの未定乗数法 - 機械学習に詳しくなりたいブログ

制約条件のもとで関数の極値を求める手法です。グラフで図示しやすいので2変数関数 $f(x,y)$ を考えます。 $g(x,y)=0$ という制約条件のもとで $f(x,y)$ を最大にする $(x,y)$ を求めることが目標です。

まずは問題の前提を再確認。 $f(x,y)$ は曲面、 $g(x,y)=0$ は曲線で表されます。つまりこの問題は、曲線 $g(x,y)=0$ 上で $f(x,y)$ が最大となる点 $(x,y)$ を求めると言い換えられます。そのような点 $(x,y)$ では、 $f(x,y)=c$ で表される等高線と $g(x,y)=0$ が接しているはずです。もし等高線と接しておらず、交差していれば、 $(x,y)$ を微小量移動した点では $f(x,y)$ の値が変化しているはずなので、極値にはなりません。そして点 $(x,y)$ で $f(x,y)=c$ と $g(x,y)=0$ が接しているときは、 $\nabla f$ と $\nabla g$ が平行であるはずです。なぜなら $\nabla f$ は等高線 $f(x,y)=c$ の法線ベクトルであり、 $\nabla g$ は曲線 $g(x,y)=0$ の法線ベクトルですから、接点では $\nabla f$ と $\nabla g$ は平行です。（参考：法線ベクトルと勾配）　

図示すれば、

のようになります。

左図は曲面 $f(x,y) = -(x^{2}+y^{2})$ 上を $y-2x+3=0$ で表される直線が通っている図です。（図の作りやすさで曲線ではなく直線にしました）*1　右図は曲面の等高線と直線、および接点における法線ベクトルを図示しています。これを見れば、等高線と接する点が極値になっていることは直感的にわかりますね。なお極値では等高線と $g(x,y)=0$ が必ず接していますが、接していても必ず極値であるとは限りません。ある方向から曲線が等高線に近づき接し、その後反対方向に抜けていけば極値にはなりません。*2　以上の説明は数学的な厳密性には欠けるでしょうが、直感的な理解には足りるかと思います。

さて、接点において $\nabla f$ と $\nabla g$ は平行であるため、ある定数 $\lambda$ が存在し

$\nabla f = \lambda \nabla g \tag{1}$

と書けます。平行であっても大きさや向きが等しいは限らないので定数倍が必要です。これを変形すれば

$\nabla (f- \lambda g) = O \tag{2}$

です。*3　この式(2)から解が求められます。ここで

$L(x,y,\lambda) = f(x,y) - \lambda g(x,y) \tag{3}$

とおけば、式(2)は

$\displaystyle \frac{\partial L}{\partial x}=0,\frac{\partial L}{\partial y}=0 \tag{4}$

であることに等しいです。さらに制約条件 $g(x,y)=0$ は $\displaystyle \frac{\partial L}{\partial \lambda}=0$ とも書けますので、まとめると式(3)において

$\displaystyle \frac{\partial L}{\partial x}=0,\frac{\partial L}{\partial y}=0,\frac{\partial L}{\partial \lambda}=0 \tag{5}$

となる $(x,y)$ が求める解です。 $(x,y)$ のみが求めたい場合 $\lambda$ は求める必要がないため、未定乗数法と呼ばれるそうです。

さて簡単のために2変数関数、1つの制約条件を考えましたが、一般的にn変数、m個の制約条件を考えることができ、 $f(x_{1},x_{2}, \cdots ,x_{n})$ の制約条件 $g_{1}(x_{1},x_{2}, \cdots ,x_{n}) = 0 , \cdots , g_{m}(x_{1},x_{2}, \cdots ,x_{n}) = 0$ における極値は

$\displaystyle L(x_{1}, \cdots ,x_{n}, \lambda_{1}, \cdots ,\lambda_{n}) = f(x_{1}, \cdots ,x_{n}) - \sum_{j=1}^{m}\lambda_{j}g_{j}(x_{1}, \cdots ,x_{n}) \tag{6}$

を $\displaystyle \frac{\partial L}{\partial x_{i}}=0, \frac{\partial L}{\partial \lambda}=0$ として解が求められます。*4　今回は制約条件が等式の場合でしたが、不等式の場合は不等式制約におけるラグランジュの未定乗数法（KKT条件）を参照ください。