ラグランジュの未定乗数法(勾配ベクトルと等式制約)

ラグランジュの未定乗数法(勾配ベクトルと等式制約)

 

では、具体的に

制約条件:$$t_i({}^t\!\boldsymbol{w}\cdot\boldsymbol{x_i}+\theta_0) \geq 1$$

での
目的関数:
$$\max_{\boldsymbol{w},\theta}d_i=\max_{\boldsymbol{w},\theta_0}\frac{1}{\sqrt{{}^t\!\boldsymbol{w}\cdot\boldsymbol{w}}}$$

をどうやって解くかというと、これには最適化という
学問領域の話になります。

ある制約条件上での目的変数の最大化や最小化を図るものです。

例えば、「店の人件費を~円以下」で「利益を最大化」
のような問題を解く時に使います。

最適化にも色々手法がありますが、今回は
「ラグランジュの未定乗数法」を使います。

かなりイメージしづらいですが本ブログでわからなければ
他の資料を参考にして、必ず理解しておいて欲しいところです。

普通の参考書に載ってる公式をそのまま書いちゃうと全く理解せずに
そのままKKT条件に行っちゃった時に苦労するのでまず高校数学Ⅱ
くらいのイメージで文章だけでつっ走ります。

まず、例として
制約条件:$$x+y-4=0$$上で
$$x^2+y^2$$を最大化させることとします。

「~上最大」で、ということは
\(x+y-4=0\)と\(x^2+y^2\)は
交点かつ接点を持つこととなります。
接点でなければ、それは最大、最小とは
呼べません。
解が制約条件上であるのは当然で
それに合わせて目的関数の値を動かしたとき
ぴったり制約条件と目的関数が接する場所が
最大もしくは最小となるはずです。

「接点を持つ」ということは、
①同じ座標上で
②共通接線
を持つ

ということになります。(数学Ⅱ)

ここで、数学Ⅱ範囲ではありませんが「勾配ベクトル」
いう概念が必要になります。

接線を考える時、今まで導関数(微分)を求めてきました。

ですが、多変量関数である時(変数がxとかyとかいっぱいあるとき)
一概に導関数を使えません。

\(y=x^2+x\)とかなら
yの増加量はxで表すことができますが
\(z=x^2+x+y^3+4y^2\)とかになっちゃうと

xで微分して、xを動かした時の増減を見ても
全然関係なくyが動くのでzがどうなるか一概にわかりません

そんな時に「勾配ベクトル」を考えます。
そんな時と言ってますが、いつでもこれで考えてください。

では、「勾配ベクトル」とはなんなのか?
すごい大雑把な説明になってしまいますが、
滑り台をイメージしてください。

滑り台のど真ん中に点を打ったとして、どの方向が下りの
方向ですか?

もちろんそれは滑る先の方向なんですが、
ちょっと斜め向きでも確かに下りの方向と言えます。

滑り台のど真ん中に点を打ってるなら、
180°は上がりの方向、180°は下りの方向みたいになってますよね。
真横は一旦置いといて

なので「一番上がる方向」を算出します。

一番上がる方向は、関数f(x,y)に対し
$$\nabla f=(\frac{ \partial f }{ \partial x },\frac{ \partial f }{ \partial y })$$
と書きます。
これは、変数の分だけ要素を持つ、
ベクトルであることに注意してください。

偏微分に関しては大丈夫だと思いますが、
その下の変数でのみ微分したら良いです。
$$\frac{ \partial f }{ \partial x }$$は
x以外を定数と見なして、fをxで微分するってことです。
ちなみに
$$\nabla f$$はナブラfと読みます。

では、改めて
制約条件:$$x+y-4=0$$上で
$$x^2+y^2$$を最大化させることとします。

$$g(x,y)=x+y-4=0$$
$$f(x,y)=x^2+y^2$$
の二つの共通接線を考えます。
制約条件と目的関数の二つでそれぞれ
勾配ベクトルを考えると

制約条件:
$$\nabla g=(\frac{ \partial g }{ \partial x },\frac{ \partial g }{ \partial y })$$
実際の\(x+y-4=0\)を入れてみると
$$\nabla g=(\frac{ \partial (x+y-4)}{ \partial x },\frac{ \partial (x+y-4) }{ \partial y })$$

$$\nabla g=(1,1)$$

次に、目的関数\(f(x,y)=x^2+y^2\)を考えると
$$\nabla f=(\frac{ \partial (x^2+y^2)}{ \partial x },\frac{ \partial (x^2+y^2) }{ \partial y })$$
$$\nabla f=(2x,2y)$$

となります。
この二つのベクトルの向きが一致していれば
このfとgは「共通接線を持つ」と言えます。
(必要条件)

向きや大きさはどうでもいいです。
それを式にすると
$$\nabla f =\lambda \nabla g$$
となります。
\(\lambda\)は大きさや、向きを考えなくて良いようにするためのパラメータです。
そして、この\(\lambda\)が「未定乗数」に当たる部分です。

今、
$$\nabla f=(2x,2y)$$
$$\nabla g=(1,1)$$
を考えると

$$\left( \begin{array}{c} 2x \\ 2y \\ \end{array} \right)=\lambda\left( \begin{array}{c} 1 \\ 1 \\ \end{array} \right)$$
となります。
解くと、
$$2x=\lambda \tag{1}$$
$$2y=\lambda \tag{2}$$
となり、
$$x=y\tag{3}$$
となります。
元の制約条件、\(x+y-4=0\)に入れると
$$x=2,y=2$$となります。

これが、制約条件を満たしつつ
目的関数を最大化させるx,yになります。

ちなみにその時の目的関数の値は

$$f(x,y)=x^2+y^2$$
$$\Downarrow$$
$$f(2,2)=2^2+2^2=8$$

そしてその時、制約条件は
$$x+y-4=0$$
$$\Downarrow$$
$$2+2-4=0$$
で満たしています。

この時、偶然
制約条件もぴったり0で満たしていますが
$$\nabla f(x,y) =\lambda \nabla g(x,y)$$
だけではg(x,y)=0を満たすとは限りません。
なのでg(x,y)=0を満たすかもチェックしなくてはいけません。

少し話が逸れますが
制約条件は範囲の端点が良いです。
g(x,y)=0の時は0に決まってますから端点もくそもないですが
覚えておいてください。
制約条件を等式で満たす時、「制約条件がアクティブ」と言います。

今回はg(x,y)=0なので絶対アクティブでないとそもそも
条件を満たしませんが
g(x,y)>=0などの時はg(x,y)=0の時をアクティブと言います。

話を戻して、
$$g(x,y)=x+y-4\tag{制約}$$
$$f(x,y)=x^2+y^2\tag{目的}$$

の時、
$$\nabla f(x,y) =\lambda \nabla g(x,y)$$
であれば良かったので、

式変形すると
$$\nabla f(x,y) -\lambda \nabla g(x,y)=0$$

となるようなx,yが必要条件でかつ制約条件を満たす、つまり
g(x,y)=0の二つを満たす必要があります。

ではもうちょっと一般的にします。

目的変数は一つですが、f(x,y)の二変数関数だったものを
n変数関数にして、制約条件もg(x,y)一つだったものを
\(h_{i}(x,y)(i=1,2,3,\cdots,m)\)とm個作ります。

まとめると
$$\boldsymbol{x}=(x_1,x_2,\cdots,x_n)\tag{変数}$$
$$h_i(\boldsymbol{x})=0\tag{制約条件}$$
$$f(\boldsymbol{x})\rightarrow最大or最小\tag{目的関数}$$

といった感じに一般形にします。
(ただし、n>m)

こうして、先ほどは勾配ベクトルにλをかけてましたがこの段階で
使用して式を先に作ってしまいます。
以下の関数を突然考えます。

$$L(\boldsymbol{x},\boldsymbol{\lambda})=f(\boldsymbol{x})+\displaystyle \sum_{ i = 1 }^{ m }\lambda_i h_i(x)$$

と\(L(\boldsymbol{x},\boldsymbol{\lambda})\)を定義します。

ちょっと展開してみると
$$L(\boldsymbol{x},\boldsymbol{\lambda})=f(\boldsymbol{x})+\lambda_1 h_1(x)+\lambda_2 h_2(x)+\cdots+\lambda_m h_m(x)$$

となり、\(h_i(x)\)は制約条件で複数個あり、
\(\lambda_i\)は制約条件毎に応じてつく未定乗数です。
この時点で変数はxがn個あって、制約条件毎に\(\lambda\)があるので制約条件の個数、m個
足して(n+m)個変数がある関数になっています。

さっきまでの勾配ベクトルの話はどこに行ったのかという話に
なっちゃいますが、このLを一回ずつ全ての変数で偏微分すると

x側(n回)の偏微分
$$\frac{ \partial L }{ \partial x_j }=\frac{ \partial f(\boldsymbol{x}) }{ \partial x_j }+\sum_{ i = 1 }^{ m } \lambda_i \frac{\partial h_i(x) }{ \partial x_j }  (j=1,2,3,\cdots,n)$$

\(\lambda\)側(m回)の偏微分
$$\frac{ \partial L }{ \partial \lambda_i}=
\frac{ \partial f(\boldsymbol{x}) }{ \partial \lambda_i}
+\sum_{ i = 1 }^{ m } {\frac{ \partial \lambda_j}{\partial \lambda_i } h_i(x)} (i=1,2,\cdots,m)$$

となります。
\(\lambda\)側(m回)の偏微分の式について展開すると

$$\frac{ \partial L }{ \partial \lambda_i}=
\frac{ \partial f(\boldsymbol{x}) }{ \partial \lambda_i}
+{\frac{ \partial \lambda_1}{\partial \lambda_i } h_1(x)+\frac{ \partial \lambda_2}{\partial \lambda_i } h_2(x)} +\cdots+\frac{ \partial \lambda_i}{\partial \lambda_i } h_i(x)+\cdots+\frac{ \partial \lambda_m}{\partial \lambda_i } h_m(x)  (i=1,2,\cdots,m)$$

と展開できて、
$$\frac{ \partial f(\boldsymbol{x}) }{ \partial \lambda_i}$$
の部分は、\(f(\boldsymbol{x})\)には\(\lambda_i\)どころか
\(\boldsymbol{\lambda}\)に関わる部分がないので0に

シグマが展開されている項は\(\lambda_i\)が変数に出てくるのは
$$\frac{ \partial \lambda_i}{\partial \lambda_i } h_i(x)$$
の部分だけで、他の項は全て0です。
\(\lambda_1,\lambda_2,\cdots,\lambda_m \)
が全て違う変数であることと、今偏微分しているのは、
\(\lambda_i\)であることに注意してください。

ということをまとめると
$$\frac{ \partial L }{ \partial \lambda_i}=h_i(\boldsymbol{x}) (i=1,2,\cdots,m)$$
となります。

再掲すると

x側(n回)の偏微分
$$\frac{ \partial L }{ \partial x_j }=\frac{ \partial f(\boldsymbol{x}) }{ \partial x_j }+\sum_{ i = 1 }^{ m } \lambda_i \frac{\partial h_i(x) }{ \partial x_j }  (j=1,2,3,\cdots,n)$$

\(\lambda\)側(m回)の偏微分
$$\frac{ \partial L }{ \partial \lambda_i}=h_i(\boldsymbol{\lambda}) (i=1,2,\cdots,m)$$

となり、それぞれ「=0」とすると
$$\frac{ \partial L }{ \partial x_j }=\frac{ \partial f(\boldsymbol{x}) }{ \partial x_j }+\sum_{ i = 1 }^{ m } \lambda_i \frac{\partial h_i(x) }{ \partial x_j } =0 \tag{①}$$

$$\frac{ \partial L }{ \partial \lambda_i}=h_i(\boldsymbol{x})=0 \tag{②}$$

という状態です。

①を変形すると
$$\frac{ \partial f(\boldsymbol{x}) }{ \partial x_j }=-(\sum_{ i = 1 }^{ m } \lambda_i \frac{\partial h_i(x) }{ \partial x_j })  \tag{①’}$$
となり、シグマを展開すると
$$\frac{ \partial f(\boldsymbol{x}) }{ \partial x_j }=-( \lambda_1 \frac{\partial h_1(x) }{ \partial x_j }+ \lambda_2 \frac{\partial h_2(x) }{ \partial x_j }+\cdots+\lambda_m \frac{\partial h_m(x) }{ \partial x_j })\tag{①’}$$
です。

また、それがj=1,2,・・・,n
個あるので①はn個あり、
$$\frac{ \partial f(\boldsymbol{x}) }{ \partial x_1 }=-( \lambda_1 \frac{\partial h_1(x) }{ \partial x_1 }+ \lambda_2 \frac{\partial h_2(x) }{ \partial x_1 }+\cdots+\lambda_m \frac{\partial h_m(x) }{ \partial x_1 })$$
$$\frac{ \partial f(\boldsymbol{x}) }{ \partial x_2}=-( \lambda_1 \frac{\partial h_1(x) }{ \partial x_2 }+ \lambda_2 \frac{\partial h_2(x) }{ \partial x_2 }+\cdots+\lambda_m \frac{\partial h_m(x) }{ \partial x_2 })$$
$$\vdots$$
$$\frac{ \partial f(\boldsymbol{x}) }{ \partial x_n}=-( \lambda_1 \frac{\partial h_1(x) }{ \partial x_n }+ \lambda_2 \frac{\partial h_2(x) }{ \partial x_n }+\cdots+\lambda_m \frac{\partial h_m(x) }{ \partial x_n })$$
とn個の方程式が生まれます。

この①が先ほどの例でいうところ「共通接線を持つ」
という
$$\nabla f(x,y) =\lambda \nabla g(x,y)$$
と同値です。

上の連立法定式から
$$\left( \begin{array}{c}
\frac {\partial f(\boldsymbol{x} ) } {\partial x_1} \\
\frac {\partial f(\boldsymbol{x} ) }{\partial x_2} \\
\vdots\\
\frac {\partial f(\boldsymbol{x})}{\partial x_n}  \end{array} \right)=-
\left( \begin{array}{c}
( \lambda_1 \frac{\partial h_1(x) }{ \partial x_1 }+ \lambda_2 \frac{\partial h_2(x) }{ \partial x_1 }+\cdots+\lambda_m \frac{\partial h_m(x) }{ \partial x_1 })\\
( \lambda_1 \frac{\partial h_1(x) }{ \partial x_2 }+ \lambda_2 \frac{\partial h_2(x) }{ \partial x_2 }+\cdots+\lambda_m \frac{\partial h_m(x) }{ \partial x_2 })
\\
\vdots \\
( \lambda_1 \frac{\partial h_1(x) }{ \partial x_n }+ \lambda_2 \frac{\partial h_2(x) }{ \partial x_n }+\cdots+\lambda_m \frac{\partial h_m(x) }{ \partial x_n })
\end{array} \right)$$

が導かれて
左辺は
「目的関数の全ての変数一つずつで偏微分した」勾配ベクトル
右辺は
「制約条件の全ての変数一つずつで偏微分した」勾配ベクトルに、制約条件毎に\(\lambda\)をかけたもの

になっているからです。

よって、最初の幾何学的イメージである、
「目的関数と制約条件が共通接線を持つ」+「制約条件を満たす(=0である)」
ということと最初から\(L(\boldsymbol{x},\boldsymbol{\lambda})\)
という変数を作って

$$\frac{ \partial L }{ \partial x_j }=\frac{ \partial f(\boldsymbol{x}) }{ \partial x_j }+\sum_{ i = 1 }^{ m } \lambda_i \frac{\partial h_i(x) }{ \partial x_j } =0 \tag{①}$$

$$\frac{ \partial L }{ \partial \lambda_i}=h_i(\boldsymbol{x})=0 \tag{②}$$

を考えることが同じになります。

\(L(\boldsymbol{x},\boldsymbol{\lambda})\)をラグランジュ関数と言います。

参考書によってはいきなりラグランジュ関数から
①と②を公式的に使わせることがあると思いますが
KKT条件などでつまづくので

「目的関数と制約条件が共通接線を持つ」+「制約条件を満たす(=0である)」
ということを「出てくる変数全ての偏微分=0」で求められる方法

ということを理解しておくべきだと個人的に思います。

これで、制約条件が等式の最大・最小問題を
ラグランジュ関数を使って解けるようになりました。

これをラグランジュの未定乗数法と言います。
この「未定」とは
制約条件の変数に\(\lambda_i\)を入れて
実際の最適解(最大値・最小値とその時の変数の値)を求める時に
\(lambda_i\)を求める必要がないから「未定」と呼ばれています。

実際先ほどの例で最適解を求める時は
\(\lambda\)を消去して、x,yを求めたので
\(\lambda\)の値はわかりません。

 

くどいようですが改めてサマリーすると

制約条件:守らないといけない条件を
$$g_i(x)$$

目的関数:最大化、もしくは最小化したいものを
$$f(x)$$
とした時、ラグランジュ関数を考えます。

\(L(\boldsymbol{x},\boldsymbol{\lambda})=\)
$$f(x)+\displaystyle \sum_{ i = 1 }^{ n } \lambda_i g_i$$

これをxと\(\lambda_i\)で全てひとつずつ偏微分して
=0になるところが、「共通接線を持つ」ところであり
「制約条件を満たすところ」になります。

次は、「不等式制約とKKT条件」について行います。

 

SNSでもご購読できます。

コメント

  1. Elvera より:

    safe loans online
    payday loans
    payday loans in nc

  2. 4 dicas de SEO para e-commerce より:

    gostei muito a forma com que seu blog
    falaram do assunto . Voce tocou pontos que realmente
    fazem a diferença. Parabéns https://vigrx1plus4.wordpress.com/2017/04/26/vigrx-plus-warning-facet-effects/

コメントを残す