ラグランジュの未定係数法のバックアップの現在との差分(No.2)

更新
追加された行はこの色です。
削除された行はこの色です。
[[量子力学Ⅰ]]

* 概要 [#f4d9cac4]
* 目次 [#w47159e5]
&katex();
#contents

&math(f(x_1,x_2,\dots,x_n)); について、
* 解きたい問題の例 [#f4d9cac4]

拘束条件 &math(g_i(x_1,x_2,\dots,x_n)=0\ \ \ (i=1\dots m)); ただし &math((m<n))); の下での停留点を探したい。
#ref(lagrange-example.svg,around,right);

** キモ [#x9a84277]
例えば、「２次元平面の $(3,2)$ を中心に書かれた半径１の円周上の点のうち、
原点からの距離が最小となるものを探す」という問題を考える。

&math(\bm x=(x_1,x_2,\dots,x_n)); を &math(n); 次元空間のベクトルと考えると、
&math(\bm x); は拘束条件を満たす方向にしか動かせないので、
そのような方向へ動かした際に &math(\Delta f=0); となることが
「拘束条件下での停留点」の意味するところである。
これは、

拘束条件を満たさない方向へ動かしたときに &math(\Delta f\ne 0); となっても構わないということ。
- 原点からの距離を表す関数 $f(x,y)=\sqrt{x^2+y^2}$ を、
- 点が円周上にあるという条件~
　$g(x,y)=(x-3)^2+(y-2)^2-1^2=0$~
の下で最小化する

という問題と捉えられる。

* 条件付き最適化問題 [#t6a56485]

上記のような問題を一般化して、

ある関数 $f(x_1,x_2,\dots,x_n)$ を最大化・最小化するような点を

$m$ 個の拘束条件

　$g_1(x_1,x_2,\dots,x_n)=0$ ~
　$g_2(x_1,x_2,\dots,x_n)=0$ ~
　$\ \ \ \vdots$ ~
　$g_m(x_1,x_2,\dots,x_n)=0$ 

の下で探すという問題を考える。((ただし $(m<n)$ とする。さもないと拘束条件が多すぎて、それだけで点が定まってしまう))

このような問題は「条件付き最適化問題」などと呼ばれる。

これを解くにはまず、与えられた拘束条件の下で関数 $f$ の ___停留点___ を探すことになる。
停留点は極小・極大・鞍点のいずれかになるが、それらのうちいずれかが最適解を与える。

この停留点の探索に、以下に説明する ___ラグランジュの未定係数法___ と呼ばれる手法が非常に役に立つ。

* ラグランジュの未定係数法 [#v1fe15da]

未定係数 &math(\lambda_i); を用いて
「未定係数」と呼ばれる実数定数 $\lambda_i$ $(i=1,2,\dots,m)$ を用いて最適化したい関数 $f$ と条件式 $g_i$ の線形結合からなる関数 $L$ を

&math(L(x_1,x_2,\dots,x_n)=f(x_1,x_2,\dots,x_n)+\sum_i \lambda_i g_i(x_1,x_2,\dots,x_n));
$$L(x_1,x_2,\dots,x_n)=f(x_1,x_2,\dots,x_n)-\sum_{i=1}^m \lambda_i g_i(x_1,x_2,\dots,x_n)$$

を構成し、
のように構成し、

&math(\frac{\partial L}{\partial x_1}=\frac{\partial L}{\partial x_2}=\dots=\frac{\partial L}{\partial x_n}=0);
$$\frac{\partial L}{\partial x_1}=\frac{\partial L}{\partial x_2}=\dots=\frac{\partial L}{\partial x_n}=0$$

&math(\frac{\partial L}{\partial \lambda_1}=\frac{\partial L}{\partial \lambda_2}=\dots=\frac{\partial L}{\partial \lambda_m}=0);
$$\frac{\partial L}{\partial \lambda_1}=\frac{\partial L}{\partial \lambda_2}=\dots=\frac{\partial L}{\partial \lambda_m}=0$$

を満たす点 &math(\bm x); およびその点における係数 &math(\lambda_i); を見つければ、
その点が停留点となる。
のすべてを満たす点 $(x_1,x_2,\dots,x_n)$ およびその点における係数 $\lambda_i$ を見つければ、
その点が $f$ の停留点となる。

また逆に、全ての停留点に対して上記の条件式を満足する係数 &math(\lambda_i); が存在する。
また逆に、全ての停留点に対して上記の条件式を満足する係数 $\lambda_i$ が存在する。

** 条件式の意味 [#h726f0a8]
すなわち、上の条件式はその点が停留点であるための必要十分条件になっている。

&math(x_j); での微分は、
というのがラグランジュの未定係数法である。

&math(\frac{\partial L}{\partial x_j}=\frac{\partial f}{\partial x_j}+\sum_i \lambda_i\frac{\partial g}{\partial x_j}=0);
この方法は量子力学の変分法をはじめ様々な分野において複雑な条件の下で目的関数の最適化を行うための非常に強力な手段となる。

などとなるから、ベクトル表記を使えば &math(n); 本の条件をまとめて、
以下、なぜこの方法で停留点が見つかるのかを解説する。

&math(\bm \nabla L=\bm \nabla f+\sum_i \lambda_i \bm \nabla g_i=\bm 0);
** 未定係数法の条件式の意味をベクトルの言葉で考える [#h726f0a8]

と書ける。
$\lambda_i$ での微分からは元の拘束条件が現れ、

&math(\lambda_i); での微分からは元の拘束条件が現れるのみである。
$$g_i(x_1,x_2,\dots,x_n)=0$$

* 停留点の十分条件となっていること [#j4fbf759]
これは $n$ 次元ベクトル $\bm x=(x_1,x_2,\dots,x_n)$ で表される点がすべての拘束条件を満たすことに対応する。

ベクトル &math(\bm x); を &math(\Delta \bm x); だけ動かしたときの &math(L); の変化は、
一方、$x_j$ での微分からは、

&math(
\Delta L=\bm \nabla L\cdot\Delta \bm x
&=\bm \nabla f\cdot \Delta \bm x+\sum_i \lambda_i \bm \nabla g_i\cdot \Delta \bm x\\
&=\Delta f+\sum_i\lambda_i\Delta g_i\\
&=\bm 0);
$$\frac{\partial L}{\partial x_j}=\frac{\partial f}{\partial x_j}-\sum_{i=1}^m \lambda_i\frac{\partial g}{\partial x_j}=0$$

と書ける。
を得る。$j=1,2,\dots,n$ の方程式をまとめてベクトル形式とすれば、

&math(\Delta \bm x); がすべての &math(g_i); の値を変化させない方向であった場合、
&math(\Delta g_1=\Delta g_2=\dots=\Delta g_m=0); であるから、&math(\Delta L=0); 
の条件はそのまま &math(\Delta f=0); の条件と一致する。
$$\bm \nabla L=\bm \nabla f-\sum_{i=1}^m \lambda_i \bm \nabla g_i=\bm 0$$

すなわち、ラグランジュの未定係数法により見つかった点は必ず停留点となることが分かる。
と書け、変形すると、

* 停留点の必要条件となっていること [#e0c73b69]
$$\bm \nabla f=\sum_{i=1}^m \lambda_i \bm \nabla g_i$$

逆に、停留点であれば必ずラグランジュの未定係数法の条件式を満たす &math(\lambda_i); 
が存在するだろうか？
となるから両者を合わせれば、 

流れ：
　(1) すべての拘束条件を満たし、~
　(2) さらに $\bm \nabla f$ が $\bm \nabla g_i$ の一次結合で表せるような点 $\bm x$ が停留点である

+ 重複する条件を取り除く &math((m\to m'));
+ &math(n-m'); 次元の &math(\Delta f=0); となる空間が存在する
+ １つの &math(\Delta g_i); のみが変化する方向に動かして &math(\lambda_i); を決めると、
その方向を加えた空間で &math(\Delta L=0); にできる
+ &math(m'); 個全てについて行えば、全 &math(n); 次元空間で &math(\Delta L=0); にできる
というのがラグランジュの未定係数法の条件式の意味するところである。

制約条件を満たすある停留点からの変位 &math(\Delta\bm x); を &math(n); 次元ベクトル空間 &math(K^n); 
から選ぶことを考える。
* どうしてこれで停留点が見つかるのか？ [#ddf68632]

移動先で制約条件が満たされている条件は &math(\bm\nabla g_i\cdot\Delta\bm x=0); だから、
１つの制約条件を与えると、制約条件を満たす変位の作る空間 &math(V_\mathrm{meet}); 
の次元は１つ減る。
以下ではなぜ (1), (2) の条件が停留点を与えるかを考える。

&math(m); 個すべての &math(\bm\nabla g_i); が線形独立であれば、
すべての制約条件を満たす変位の作る空間は &math(n-m); 次元となるが、
いくつかが線形従属である場合にはそれらを取り除いて独立な条件を &math(m'); 個残す。
** 考え方のキモ [#x9a84277]

すると、&math(\dim V_\mathrm{meet}=n-m'); となる。
そもそも「拘束条件下での停留点」とはどういう性質を持つべきかを考えると、

&math(\Delta\bm x\in V_\mathrm{meet}); に対しては &math(\Delta L=\Delta f); であるから、
停留点の条件 &math(\Delta f=0); によりラグランジュの未定係数法の条件式は成立する。
　(1) $\bm x=(x_1,x_2,\dots,x_n)$ が $n$ 次元空間において拘束条件を満たす点であり~
　(2)' $\bm x\to\bm x+\Delta\bm x$ の $\Delta \bm x$ を「拘束条件を破らない方向に取る限り」 ~
　　 そこでの $f$ の一次の変位量がゼロとなる $\Delta f=\bm\nabla f\cdot\Delta\bm x=0$~

を満たせばよいことに気づく。

拘束条件を破るような方向へ動かしたときに $\Delta f\ne 0$ となっても構わないところがキモである。

(1) はラグランジュの未定係数法の条件(1)と一致するので、
以下では (2)' と (2) が同値であることを理解したい。

そこで (2)' をベクトルの言葉で書きなおそう。

$\Delta \bm x$ を拘束条件を破らない方向に取る、すなわち $\Delta g_i=0$ は、

$$\bm\nabla g_i\cdot\Delta \bm x=0$$ 

と表せ、また $f$ の変化の一次成分がゼロ $\Delta f=0$ は

$$\bm\nabla f\cdot\Delta \bm x=0$$

に書き換えられるから、(2)' は

　すべての $i$ について $\bm\nabla g_i\perp\Delta \bm x$、であれば $\bm\nabla f\perp\Delta \bm x$ である

と言い換えられる。

** 停留点の十分条件となっていること [#j4fbf759]

(2) を満たす点 $\bm x$ が必ず (2)' を満たすことは以下のように理解できる。

(2) が成り立つ、つまり

$$\bm\nabla f=\sum_i \lambda_i \bm\nabla g_i$$

のとき、すべての $\bm\nabla g_i$ が $\Delta \bm x$ に垂直ならば明らかに $\bm\nabla f$ も $\Delta \bm x$ に垂直である。

$$\because\bm\nabla f\cdot\Delta \bm x=\sum_i \lambda_i \underbrace{\bm\nabla g_i\cdot\Delta \bm x}_{=\,0}=0$$

** 停留点の必要条件となっていること [#e0c73b69]

逆に、(2)' から (2) が言えるだろうか？

$\bm\nabla f$ が $\bm\nabla g_i$ の線形結合で表せない可能性を考えて、

$$\bm\nabla f=\sum_j \lambda_j\bm\nabla g_j + \bm\delta$$

と書こう。ただし、$\bm\delta$ は任意の $j$ に対して $\bm\delta\cdot\bm \nabla g_j=0$ となるようなベクトルである。

そこで $\Delta\bm x=\bm\delta$ と取れば、$\Delta\bm x$ はすべての $\bm\nabla g_j$ に垂直であるから、
(2)' が成り立つなら $\Delta f=\bm\nabla f\cdot\bm\delta=\|\bm\delta\|^2=\bm 0$ でなければならない。

すなわち $\bm\nabla f=\sum_j \lambda_j\bm\nabla g_j$ と表せることになり (2)'→(2) が示された。

** 直交補空間を用いた解説 [#qf4edf56]

以上で証明は済んでいるのだけれど、直交補空間の概念を知っているとより直感的に理解できるので付け加える。

$\{\bm\nabla g_i\}$ により張られる線形空間を $V$ と置き、
$V_\text{meet}$ をその直交補空間とする($V_\text{meet}=V^\perp$)。

このとき任意の $\Delta \bm x\in V_\text{meet}$ はすべての $\bm\nabla g_i$ に直交するから、
$\Delta \bm x\in V_\text{meet}$ は $\Delta \bm x$ が拘束条件を破らない方向であることと同義である。

すると、任意の $\Delta \bm x\in V_\text{meet}$ に対して 
$\Delta f=\bm\nabla f\cdot\Delta\bm x=0$ が成り立つことが停留点の条件となる。

これは、$\Delta f$ が $V_\text{meet}^\perp$ の元であることを表しており、
すなわち $\Delta f\in V$ を表している。

つまり $\Delta f$ が $\{\bm\nabla g_i\}$ の線形結合として表せるのである。

これがラグランジュの未定係数法の図形的な意味である。

* まとめ [#v484cf2e]

見つけたいのは

$$
\underbrace{\bm\nabla g_i\cdot\Delta\bm x=0\ \ (i=1\dots m)}_{\Delta\bm x\,\text{は拘束条件を破らない}}
$$

を満たす任意の $\Delta\bm x$ に対して、

$$
\underbrace{\bm\nabla f\cdot\Delta\bm x=0}_{\Delta f=0\,\text{となる}}
$$

となるような点 $\bm x$ であるが、

上の条件を満たすには $\bm\nabla f$ が 
$\bm\nabla g_i$ の線形結合として表せる必要がある。

これがラグランジュの未定係数法である。

と書かれて理解できればたぶん大丈夫。

* 例題 [#f3642e93]

２次元平面の $(3,2)$ を中心に書かれた半径１の円周上の点で、
原点からの距離が最小となるものを探したい

- 原点からの距離を表す関数 $f(x,y)=\sqrt{x^2+y^2}$ を、
- 点が円周上にあるという条件 $g(x,y)=(x-3)^2+(y-2)^2-1^2=0$ の下で
- 最小化すればよい

#ref(lagrange-example.svg,around,right);

ちょっと楽をするため $f(x,y)=\sqrt{x^2+y^2}$ ではなく $f(x,y)=x^2+y^2$ を使う

$$
\begin{aligned}
\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]\\
\end{aligned}
$$

$\lambda,x,y$ で微分すると、

$$
\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}
$$

第２式、第３式より

$$x=\frac{3\lambda}{\lambda-1},y=\frac{2\lambda}{\lambda-1}$$ 

となるから、求める点は直線 $y=2x/3$ の上にあることが分かる。

$t=\frac{\lambda}{\lambda-1}$ と置いて第１式に代入すると、

$$
\begin{aligned}
&(3t-3)^2+(2t-2)^2=1\\
&13(t-1)^2=1\\
&t=1\pm \frac{1}{\sqrt{13}}\\
\end{aligned}
$$

$x=3t,y=2t$ に代入しなおして、

$$
x=3\Big(1\pm \frac{1}{\sqrt{13}}\Big),\ y=2\Big(1\pm \frac{1}{\sqrt{13}}\Big)\\
$$

ただし複号同順。このうち原点に近いのは 

$$
x=3\Big(1- \frac{1}{\sqrt{13}}\Big),\ y=2\Big(1- \frac{1}{\sqrt{13}}\Big)\\
$$

であり、もう一方は最大値を与える。

ラグランジュの未定係数法の言うところでは、
これらの点では円弧と $\bm\nabla f$ とが直交するため、
円弧の上で $f$ が停留値を取る。

もちろんこのような単純な問題であれば図形を書いて解くことも可能だが、
ラグランジュの未定係数法を用いることで問題設定に依らず、また多次元であっても、
「条件付き最適化問題」を機械的に解けることを理解せよ。

#collapsible(Mathematicaソース)

 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
 ]

#collapsible(end)

* 参考文献 [#dd54f218]

-ラグランジュの未定乗数法の解説と直感的な証明~
http://www.yunabe.jp/docs/lagrange_multiplier.html

* コメント・質問 [#v8dfb2fb]

#article_kcaptcha
Counter: 19824 (from 2010/06/03), today: 5, yesterday: 16