ラグランジュの未定係数法 の履歴(No.13)
更新目次†
解きたい問題の例†
例えば、「2次元平面の $(3,2)$ を中心に書かれた半径1の円周上の点のうち、 原点からの距離が最小となるものを探す」という問題を考える。
これは、
- 原点からの距離を表す関数 $f(x,y)=\sqrt{x^2+y^2}$ を、
- 点が円周上にあるという条件
$g(x,y)=(x-3)^2+(y-2)^2-1^2=0$
の下で最小化する
という問題と捉えられる。
条件付き最適化問題†
上記のような問題を一般化して、
ある関数 $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$
の下で探すという問題を考える。*1ただし $(m<n)$ とする。さもないと拘束条件が多すぎて、それだけで点が定まってしまう
このような問題は「条件付き最適化問題」などと呼ばれる。
これを解くにはまず、与えられた拘束条件の下で関数 $f$ の 停留点 を探すことになる。 停留点は極小・極大・鞍点のいずれかになるが、それらのうちいずれかが最適解を与える。
この停留点の探索に、以下に説明する ラグランジュの未定係数法 と呼ばれる手法が非常に役に立つ。
ラグランジュの未定係数法†
「未定係数」と呼ばれる実数定数 $\lambda_i$ $(i=1,2,\dots,m)$ を用いて
$$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)$$
という関数を構成し、
$$\frac{\partial L}{\partial x_1}=\frac{\partial L}{\partial x_2}=\dots=\frac{\partial L}{\partial x_n}=0$$
$$\frac{\partial L}{\partial \lambda_1}=\frac{\partial L}{\partial \lambda_2}=\dots=\frac{\partial L}{\partial \lambda_m}=0$$
のすべてを満たす点 $(x_1,x_2,\dots,x_n)$ およびその点における係数 $\lambda_i$ を見つければ、 その点が停留点となる。
また逆に、全ての停留点に対して上記の条件式を満足する係数 $\lambda_i$ が存在する。
すなわち、上の条件式はその点が停留点であるための必要十分条件になっている。
というのがラグランジュの未定計数法であった。
以下、なぜこの方法で停留点が見つかるのかを解説する。
未定係数法の条件式をベクトルの言葉で書きなおす†
$\lambda_i$ での微分からは元の拘束条件が現れるのみであり、
$$g_i(x_1,x_2,\dots,x_n)=0$$
これは $n$ 次元ベクトル $\bm x=(x_1,x_2,\dots,x_n)$ で表される点がすべての拘束条件を満たすことと同義である。
一方、$x_j$ での微分からは、
$$\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$ の方程式をまとめてベクトル形式とすれば、
$$\bm \nabla L=\bm \nabla f-\sum_{i=1}^m \lambda_i \bm \nabla g_i=\bm 0$$
と書け、変形すると、
$$\bm \nabla f=\sum_{i=1}^m \lambda_i \bm \nabla g_i$$
となるから両者を合わせれば、
(1) すべての拘束条件を満たし、
(2) さらに $\bm \nabla f$ が $\bm \nabla g_i$ の一次結合で表せるような点 $\bm x$ が停留点である
というのがラグランジュの未定係数法の条件式の意味するところである。
考え方のキモ†
なぜ (1), (2) の条件が停留点を与えるかを考えるため、 そもそも「拘束条件下での停留点」とはどういう性質を持つべきかを考えると、
(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) はラグランジュの未定計数法の条件と一致するので、 以下では (2)' と (2) が同値であることを理解したい。
そこで (2)' をベクトルの言葉で書きなおそう。
$\Delta \bm x$ を拘束条件を破らない方向に取る、というのは、
$$\bm\nabla g_i\cdot\Delta \bm x=0$$
と表せ、また $f$ の変化の一次成分がゼロ $\Delta f=0$ は
$$\bm\nabla f\cdot\Delta \bm x=0$$
に書き換えられるから、(2)' は
$$\bm\nabla g_i\perp\Delta \bm x\to \bm\nabla f\perp\Delta \bm x$$
と言い換えられる。
停留点の十分条件となっていること†
(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$ に垂直である。
$$\bm\nabla f\cdot\Delta \bm x=\sum_i \lambda_i \underbrace{\bm\nabla g_i\cdot\Delta \bm x}_{=\,0}=0$$
停留点の必要条件となっていること†
逆に、(2)' から (2) が言えるだろうか?
$\bm\nabla f$ が $\bm\nabla g_i$ の線形結合で表せない可能性を考えて、
$$\bm\nabla f=\sum_j \lambda_j\bm\nabla g_i + \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) が示された。
まとめ†
見つけたいのは
$$ \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$ の線形結合として表せる必要がある。
これがラグランジュの未定係数法である。
と書かれて理解できればたぶん大丈夫。
例題†
2次元平面の $(3,2)$ を中心に書かれた半径1の円周上の点で、 原点からの距離が最小となるものを探したい
- 原点からの距離を表す関数 $f(x,y)=\sqrt{x^2+y^2}$ を、
- 点が円周上にあるという条件 $g(x,y)=(x-3)^2+(y-2)^2-1^2=0$ の下で
- 最小化すればよい
ちょっと楽をするため $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} $$
第2式、第3式より
$$x=\frac{3\lambda}{\lambda-1},y=\frac{2\lambda}{\lambda-1}$$
となるから、求める点は直線 $y=2x/3$ の上にあることが分かる。
$t=\frac{\lambda}{\lambda-1}$ と置いて第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$ が停留値を取る。
もちろんこのような単純な問題であれば図形を書いて解くことも可能だが、 ラグランジュの未定係数法を用いることで問題設定に依らず、また多次元であっても、 「条件付き最適化問題」を機械的に解けることを理解せよ。
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