機械学習に詳しくなりたいブログ

機械学習や数学について勉強した内容を中心に書きます。100%趣味です。記事は数学的に厳密でなかったり誤りを含んでいるかもしれません。ご指摘頂ければ幸いです。

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

制約条件のもとで関数の極値を求める手法です。グラフで図示しやすいので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:id:opabinia2:20180128120819p:plain のようになります。

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

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


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

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


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

です。*2 この式(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 として解が求められます。*3 今回は制約条件が等式の場合でしたが、不等式の場合は不等式制約におけるラグランジュの未定乗数法(KKT条件)を参照ください。

*1:この例では簡単に変数が消去できるので、ラグランジュの未定乗数法を使うまでもありません。

*2:\nabla線形性より

*3:複数の制約条件の場合は、もう少し複雑な理屈が背景にあるようです