Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2011-02-10

ラグランジュの未定乗数法のイメージ

ある一定の制約条件の下で、関数の最大値(あるいは最小値)を求めたいとき、

ラグランジュの未定乗数法」という便利な計算方法があります。

たとえば、決まった燃費の下で一番速い車を作れとか、

決まった資本を割り当てて利潤が最大になる方法を探せとか、

実際問題としてもかなり役立つ計算方法です。


さて、ある関数の最大値(あるいは最小値)を求めるには、微分して0になる点を探すという方法が定番です。

微分して0になる点というのは、「山のてっぺんか、谷の底」に相当するからです。

しかし、そこに何らかの制約条件が加わったら、どうでしょうか。

例えば Wikipediaを見ると >> wikipedia:ラグランジュの未定乗数法

 関数: f(P1,P2,P3・・・,Pn) = - Σ Pk log2 Pk が最大となる点を、

 制約条件: g(P1,P2,P3・・・,Pn) = Σ Pk - 1 が 0 となる条件の下で探し出せ、

  (P1,P2,P3・・・,Pn を全部足し合わせたら 1 となる条件の下で探し出せ、)

といった例が載っています。

これ、単純に f を Pi (i=1〜n) で微分しても答は出てきません。

制約条件があるので、答は必ずしも「山のてっぺん」ではなく、「斜面の途中」にあるかもしれないからです。

では、どうするか。

ここでλという新しい変数を用意して、

 f + λg = 0

という式を作ります。

そんでもって、この新しく作った式を Pi (i=1〜n) で微分すると、目的の関数fの最大値(又は最小値)が得られます。

これが「ラグランジュの未定乗数法」という計算方法なのです・・・

・・・なんだか、分かったような、分からないような。

なぜ、λという新しい変数が降って湧いてきたのか。

なぜこれで、最大値(あるいは最小値)が計算できるのか。謎は深まるばかりです。


単純な例で確かめてみましょう。

関数: f(x, y) = 3 x + 5 y が最大となる点を、

制約条件: g(x, y) = x^2 + y^2 - 1 が 0 となる条件の下で探し出せ。

この例であれば、グラフを描いて高校数学の知識で解くことができます。

f:id:rikunora:20110210143956p:image

答は、f : 3 x + 5 y = L という直線と、g : x^2 + y^2 = 1 という円が接した点です。

つまり x = 3/√(3^2 + 5^2), y = 5/√(3^2 + 5^2)。

図を見て思うことは、なんとなく直線を上下に動かしてみて、円と接する点を探せばよいのかな、といったところでしょうか。

しかし、この図と「ラグランジュの未定乗数法」を比べてみると、ちょっとやり方が違っています。

図では、直線fの方を L というパラメータで動かしていますが、未定乗数法では円gの方にλというパラメータが付いています。

比較のため、同じ問題を未定乗数法で解いてみましょう。

まず f + λg = 0 という式を作る

 (3 x + 5 y) + λ(x^2 + y^2 - 1) = 0   ・・・(1)

・(1)式を x で微分する。

 3 + 2 λ x = 0     ・・・(2)

・(1)式を y で微分する。

 5 + 2 λ y = 0     ・・・(3)

・(1)式を λ で微分する。

 x^2 + y^2 - 1 = 0   ・・・(4)

・(2),(3),(4) の3つの連立方程式から、x, y, λ を求める。

この計算を素直に行えば、確かに答が出てきます。

(答はプラスマイナスの2つ出てきます。一方が円に上側で接した最大値、もう一方が下側で接した最小値です)

答が出るには出たのですが、なぜ円にλなのか、いまひとつ意味がはっきりしません。


実は、どれほど平面のグラフとにらめっこしていても、未定乗数法の意味は見えてきません。

もう1つ次元を増やして3Dのグラフにして、初めて意味が見えてくるのです。

どういうことか。

上の例で、x^2 + y^2 = 1 という式を(x,y)平面上の円として見るのではなくて、

g = x^2 + y^2 - 1 という式を(x, y, g)空間の中で捉えるのです。

f:id:rikunora:20110210144029p:image

これが、g = x^2 + y^2 - 1 を空間的に捉えたイメージです。

この3Dのグラフは、水平に切れば円になるし、垂直に切れば放物線になっています。

同じ発想で、f = 3 x + 5 y という関数を(x, y, f)という空間に3D表示してみましょう。

f:id:rikunora:20110210144102p:image

こんな空間に置かれた平面となります。

それでは、この f と g を足し合わせたらどうなるか。

f:id:rikunora:20110210144137p:image

こんな具合に、放物面が斜めにずれたような形になります。

真上から見た等高線で描くと、こんな感じ。

f:id:rikunora:20110210144208p:image

f の平面が傾いている分だけ、放物面の中心が原点からずれています。

具体的には x = -3/2, y = -5/2 となっています。


以上の3Dイメージをもとに、未定乗数法に表れる f + λg という式の意味を考えてみましょう。

まず λg という項について、λの値を変化させると、3Dグラフはどのように形を変えるのか。

イメージとしては放物面のすぼみ具合というか、深さが変化するような感じになります。

λ=0 なら全くの平面、λが小さければお皿みたいに少しだけ窪んだ形、λが大きければ深く窪んだおわん型。

このλgに、f の平面を重ねて描くと、どうなるでしょうか。

f:id:rikunora:20110210144250p:image

わかるかな。

λによって放物面のすぼみ具合を変化させると、ちょうどxy平面上のところで、

放物面λg と平面fの「傾斜をぴったり一致」させることができます。

言い換えれば、傾斜がぴったり一致するようにλを調整することができる、というわけです。

この、傾斜がぴったり一致した状態で(つまり、うまいλが見つかった状態で)

改めて f + λg = 0 という足し合わせた式を3Dグラフにすると、どうなるか。

f:id:rikunora:20110210144332p:image

こんな具合に、傾斜がぴったり一致した点が、放物面の最も低い谷底に降りてきます。

ここのところわかりづらいので、3Dグラフを真横から切った状態で図解してみました。

f:id:rikunora:20110210144402p:image

図の上が、f と λg の傾きを一致させたところ。

この状態で f の傾きが0になるようにパタンと倒し込むと、λg の傾きも一致しているので、

全体として傾きの一致した点が一番低い谷底に降りてきます。

この様子を想像するに、まな板の下に何か丸くて柔らかいものがぶら下がっていて、

その先っぽにある答の点を、まな板を傾けて一番下に持ってくる、といった感じです。

・・・それっぽい色で描いてみました (^^).


そもそも微分というツールの神髄は、傾きが0となる谷底の点を探すところにあります。

何とかしてうまい具合に、答の点が一番下にくるように関数を操作したい。

そのために、目的の関数と「傾斜がぴったり一致する」ように、制約条件を適当に調整して重ね合わせる。

重ね合わせた関数=0とすると、傾斜が一致した点である目的の答が一番下に来る(あるいは一番てっぺんに来る)。

一番下に来た点は、微分によって探し当てることができる。

以上が「ラグランジュの未定乗数法」のイメージです。

よくわからなかったら、とにかく簡単な例で3Dのグラフを描いてみてください。

なんとなく実感できるようになります。

2次元のイメージ操作は思い描けても、3次元のイメージ操作は難しい。

ラグランジュの未定乗数法の難しさは、結局そこにあるのだと思います。


itaita 2011/02/11 08:55 自分はこの問題、∇fと∇gが平行になる
すなわちfの等高線とgの等高線がある点で接している、
とイメージしてます。
標高50mで地価の一番安い土地を買う問題とすると、標高の等高線と価格の等高線がある角度で交差していたら標高50m等高線をどちらかに動けばより安い土地がまだありますが、接しているともう安くできませんので。

rikunorarikunora 2011/02/11 11:53 標高と地価の等高線、なるほどな言い回し。以後、使わさせてもらいます。
実は私、最初は全くイメージが湧かず計算方法だけ覚えて、
3次元(or多次元)だと気付いたのはずいぶん後になってからなのです。

通りすがり通りすがり 2011/05/15 04:58 XYZの直行座標として、z = 3 x + 5y の平面を、gの条件でz方向にくりぬいたときの最高地点は、等高線が平行になると考えるほうがシンプルでは?

rikunorarikunora 2011/05/18 13:17 「gの条件でz方向にくりぬいた」というくだりをよく考えてみたら・・・わかりました!
gの放物面が平らになるように、全体を引っ張り上げて変形すると、答の点が最高地点に来るのですね。
言葉にすると表現しずらいけれど、たぶんアニメーションにして見れば納得がゆくと思います。

松本眞吉松本眞吉 2012/06/05 14:25 興味深い記事、ありがとうございます。
参考までに、全く代数的に考えてみました。
(1)fが点(x,y)で極値:f(x+Δx,y+Δy)=f(x,y)=d
(2)拘束条件:g(x+Δx,y+Δy)=g(x,y)=c
が成立する。(1),(2)はΔx、Δyがf=dかつg=cに沿った線上での増分であることを示している。
(1)より、∂xfΔx+∂yfΔy=0 ...(3)
(2)より、∂xgΔx+∂ygΔy=0 ...(4)
(3)から得られるΔy/Δx=-∂xf/∂yfと(4)から得られるΔy/Δx=-∂xg/∂ygとが等しいので、
∂xf/∂yf=∂xg/∂yg ...(5)
分数式は一般に、例えば2/3=2λ/3λのようになるので、(5)より、∂xf=λ∂xg、∂yf=λ∂yg
したがって、∂x(f-λg)=0, ∂y(f-λg)となる。
∂xf=λ∂xg、∂yf=λ∂ygはfのgradientのx方向成分がgのそれのλ倍で、gについても同様であることを示している。

rikunorarikunora 2012/06/19 15:42 松本様、コメント遅くなりました。
こうして式にしてみると、fとgが対称的に、とてもきれいに並んでいることに気付かされました。
私が最初に数式を見たときには、さっぱり意味がわからなかったのですが、
今改めて見直すと、なんとも美しい方法だと感じます。

mathnbmathnb 2012/07/15 12:26 制約条件 x^2+y^2=1 の もとで
4*Sqrt[(x - 1)^2 + y^2] + 3*Sqrt[(x + 1)^2 + y^2] の最大を
ここの手法で お願いいたします。

hirotahirota 2012/07/16 11:28 乗数法使うより (x,y)=(cosθ,sinθ) でやったほうが簡単じゃない

mathnbmathnb 2012/07/16 12:16 でも 敢えて ここの手法で お願いいたします

jolbjolb 2012/08/21 12:52 イメージは山に道があって、道を変えずに、景色を変化させて、道を極値に持っていく感じですね。

yyuyyyuy 2016/02/01 00:03 ラグランジュの未定乗数法の記事を拝読しました…!
公式だけ見たらちんぷんかんぷんだったのですが、
なるほどなぁと、自分の中でとてもしっくりきました。
テスト頑張ります。ありがとうございました!

rikunorarikunora 2016/02/01 10:08 私も最初はちんぷんかんぷんでした。
でも、自分なりにイメージを描く工夫を重ねると道は開ける。
テスト頑張れ!

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rikunora/20110210/p1