ラグランジュの未定係数法 の履歴(No.11)
更新目次†
解きたい問題の例†
例えば、「2次元平面の を中心に書かれた半径1の円周上の点のうち、 原点からの距離が最小となるものを探す」という問題を考える。
これは、
- 原点からの距離を表す関数 を、
- 点が円周上にあるという条件
の下で最小化する
という問題と捉えられる。
条件付き最適化問題†
上記のような問題を一般化して、
ある関数 を最大化・最小化するような点を
個の拘束条件
の下で探すという問題を考える。*1ただし とする。さもないと拘束条件が多すぎて、それだけで点が定まってしまう
このような問題は「条件付き最適化問題」などと呼ばれる。
これを解くにはまず、与えられた拘束条件の下である関数 の 停留点 を探すことになる。
その際、以下に説明する ラグランジュの未定係数法 と呼ばれる手法が非常に役に立つ。
キモ†
「拘束条件下での停留点」とは、
が 次元空間において拘束条件を満たす点であるとして、
「 を拘束条件を破らない方向に取る限り」
の一次の変位量がゼロとなる:
という意味である。
拘束条件を破るような方向へ動かしたときに となっても構わないところが キモといえる。
ラグランジュの未定係数法†
「未定係数」と呼ばれる実数定数 を用いて
という関数を構成し、
のすべての条件式を満たす点 およびその点における係数 を見つければ、 その点が停留点となる。
また逆に、全ての停留点に対して上記の条件式を満足する係数 が存在する。
すなわち、上の条件式はその点が停留点であるための必要十分条件になっている。
条件式の意味†
での微分からは元の拘束条件が現れるのみである。
一方、 での微分からは、
を得る。 の方程式をすべてまとめてベクトル形式とすれば、
と書ける。これを変形すると、
となり、すなわち両者を合わせれば、
その点ですべての拘束条件が満たされており、
なおかつ
が
の一次結合で表せるような点が停留点である
というのがラグランジュの未定係数法の条件式の意味するところである。
停留点の十分条件となっていること†
そのような点 が必ず停留点となることは、 以下のように簡単に理解できる。
が拘束条件を満たすとき、 も拘束条件を満たすためには すべての に対して
となる方向に の方向を選ばなければならない。
つまり はすべての に垂直である。
このとき条件式より、
&math( \Delta f=\bm\nabla f\cdot\Delta\bm x=\sum_i \lambda_i\underbrace{\bm\nabla g_i\cdot\Delta\bm x}_{=\,0}=0 );
となり、条件を満たす点が必ず停留点となることを確認できる。
停留点の必要条件となっていること†
逆に、すべての停留点に対して、上記の条件式を満たす が必ず存在するだろうか?
ある点 が拘束条件下での停留点であるとすれば、
- は拘束条件を満たす
- を拘束条件を満たす方向へ動かしたときに が変化しない
が成り立つが、この 2. は、
- がすべての に垂直なら、 にも垂直である
と読み替えられる。この条件と、
- は の線形結合で表せる
が同値であることを言えば良いのだが・・・
直交補空間の概念に通じているなら
2. を
・ すべての が張る空間を とし、
・ その直交補空間を とすれば、
・ 任意の が に垂直であると言い換えることができて、これは が の直交補空間、すなわち の元であることを示すから、 は を張る の線形結合で表せて、その係数が である。
ということで証明が終わるのであるが、、、前提知識の少なくて済む説明をするなら:
すべての が張る空間を とし、 そこに正規直交基底 を取る。
が の元ではない可能性を考えて、
と書く。ただし、 であり、任意の に対して とする。
すると はすべての に垂直であるから、 と取れば、
,
となって、 でない限り仮定に反する。
すなわち であり、これは が の元で、 の線形結合で表せることを意味する。
まとめ†
見つけたいのは
&math( \underbrace{\bm\nabla g_i\cdot\Delta\bm x=0\ \ (i=1\dots m)}_{\Delta\bm x\,\text{は拘束条件を破らない}} );
を満たす任意の に対して、
&math( \underbrace{\bm\nabla f\cdot\Delta\bm x=0}_{\Delta f=0\,\text{となる}} );
となるような点 であるが、
上の条件を満たすには が の線形結合として表せる必要がある。
これがラグランジュの未定係数法である。
と書かれて理解できればたぶん大丈夫。
例題†
2次元平面の を中心に書かれた半径1の円周上の点で、 原点からの距離が最小となるものを探したい
- 原点からの距離を表す関数 を、
- 点が円周上にあるという条件 の下で
- 最小化すればよい
ちょっと楽をするため ではなく を使う
&math( \mathcal{L}(x,y) &=f(x,y)-\lambda g(x,y)\\ &=x^2+y^2-\lambda\Big[(x-3)^2+(y-2)^2-1\Big]\\ );
で微分すると、
&math( \begin{cases} \frac{\partial\mathcal{L}}{\partial \lambda}=(x-3)^2+(y-2)^2-1=0\\ \frac{\partial\mathcal{L}}{\partial x}=2x-2\lambda(x-3)=2(1-\lambda)x+6\lambda=0\\ \frac{\partial\mathcal{L}}{\partial y}=2y-2\lambda(y-2)=2(1-\lambda)y+4\lambda=0 \end{cases} );
第2式、第3式より
となるから、求める点は直線 の上にあることが分かる。
と置いて第1式に代入すると、
&math( &(3t-3)^2+(2t-2)^2=1\\ &13(t-1)^2=1\\ &t=1\pm \frac{1}{\sqrt{13}}\\ );
に代入しなおして、
&math( x=3\Big(1\pm \frac{1}{\sqrt{13}}\Big),\ y=2\Big(1\pm \frac{1}{\sqrt{13}}\Big)\\ );
ただし複号同順。このうち原点に近いのは
&math( x=3\Big(1- \frac{1}{\sqrt{13}}\Big),\ y=2\Big(1- \frac{1}{\sqrt{13}}\Big)\\ );
であり、もう一方は最大値を与える。
ラグランジュの未定係数法の言うところでは、 これらの点では円弧と とが直交するため、 円弧の上で が停留値を取る。
もちろんこのような単純な問題であれば図形を書いて解くことも可能だが、 ラグランジュの未定係数法を用いることで問題設定に依らず、また多次元であっても、 「条件付き最適化問題」を機械的に解けることを理解せよ。
LANG:Mathematica Show[ ParametricPlot[{Cos[t] + 3, Sin[t] + 2}, {t, 0, 2 Pi}], ListPlot[{{0, 0}, {3, 2}, {3 (1 - 1/Sqrt[13]), 2 (1 - 1/Sqrt[13])}, {3 (1 + 1/Sqrt[13]), 2 (1 + 1/Sqrt[13])}}, PlotStyle -> PointSize[Large]], ParametricPlot[{x, 2 x/3}, {x, 0, 4}, PlotStyle -> {{Thin, Dashed}}], PlotRange -> {{0, 4}, {0, 3}}, AxesOrigin -> {0, 0}, GridLines -> {{0, 1, 2, 3, 4}, {0, 1, 2, 3}}, AspectRatio -> Automatic, ImageSize -> 200 ]
参考文献†
- ラグランジュの未定乗数法の解説と直感的な証明
http://www.yunabe.jp/docs/lagrange_multiplier.html