ラグランジュ乗数法
ラグランジュ乗数法とは、複数の変数に1つ以上の制約条件が課せられたときに、関数の停留点を求める手法です。
$D$ 次元の変数 ${\bf x}=(x_1,\cdots,x_D)$ について、制約条件(等式制約)
$$g({\bf x})=0 -①$$
の下、関数 $f({\bf x})$ を最大または最小にする変数 ${\bf x}$(停留点)は、ラグランジュ関数、
$$L({\bf x},\lambda)\equiv f({\bf x})+\lambda g({\bf x})$$
が停留値を持つ ${\bf x}$ と $\lambda$(ラグランジュ乗数)を求める問題に置換えられます。この条件は、以下で表すことができます。
$$\frac{\partial L}{\partial{\bf x}}=\nabla f+\lambda\nabla g=0 -②$$
$$\frac{\partial L}{\partial\lambda}=g=0 -③$$
ラグランジュ関数の意味
2つの条件式②と③のうち、③は制約条件①を表しているので、②について説明します。
制約条件①は $D$ 次元の超曲面であり、この超曲面上の微小変位 ${\bf\delta}$ を考えます。
$$g({\bf x}+{\bf\delta})\cong g({\bf x})+{\bf\delta}\cdot\nabla g({\bf x})$$
${\bf\delta}\to0$ の極限では、${\bf\delta}\cdot\nabla g({\bf x})\cong0$ となり、${\bf\delta}$ は超曲面①の接線であるため、$\nabla g({\bf x})$ は超曲面①に対して垂直であることが分かります。
一方、$f({\bf x})$ の停留点において $\nabla f({\bf x})$ も超平面①に対して垂直です。なぜなら、垂直でなければ、超平面①に沿って $f({\bf x})$ が増減してしまう方向があるからです。
従って、停留点において、$\nabla f({\bf x})$ と $\nabla g({\bf x})$ は平行であり、適当な定数(乗数)$\lambda$ により②で表すことができます。
カルーシュ・クーン・タッカー条件
カルーシュ・クーン・タッカー条件とは、制約条件①(等式制約)の代わりに、次の不等式制約で関数 $f({\bf x})$ を最大または最小にする変数 ${\bf x}$(停留点)を求める場合の制約条件です。
$$g({\bf x})\ge0 -④$$
このとき停留点は、$g({\bf x})\gt0$ の範囲に含まれるか、$g({\bf x})=0$ 上に存在するかの2つのケースに分けることができます。
ケース | 停留点の場所 | 条件式 | |
1 | $g({\bf x})\gt0$ | $\nabla f({\bf x})=0$ | $\lambda=0$ |
2 | $g({\bf x})=0$ | $\nabla f({\bf x})+\lambda\nabla g({\bf x})$=0 | $\lambda\ne0$ |
ケース1は $g({\bf x})$ の条件は関係なくなりますので、ラグランジュ関数で $\lambda=0$ の場合に等しくなります。ケース2は等式制約で、通常のラグランジュ関数になります。いずれの場合も、次の条件式が成り立つことが分かります。
$$\lambda g({\bf x})=0 -⑤$$
これら④と⑤は、カルーシュ・クーン・タッカー条件と呼ばれています。
簡単な例
2次元の簡単な例で考えます。
$$f(x,y)=1-x^2-y^2 , g(x,y)=x+y+1$$
このとき、ラグランジュ関数は以下になるため、
$$L=f+\lambda g=1-x^2-y^2+\lambda(x+y+1)$$
制約条件②は以下になり、
$$\frac{\partial L}{\partial x}=-2x+\lambda=0 , \frac{\partial L}{\partial y}=-2y+\lambda=0 -⑥$$
カルーシュ・クーン・タッカー条件⑤は以下になります。
$$\lambda g=\lambda(x+y+1)=0 -⑦$$
⑥を⑦に代入し、$x$ と $y$ を消去すると、
$$\lambda(\lambda+1)=0$$
より、$\lambda=0,-1$ が導かれます。この2つのケースで停留点を求めると、
- $g({\bf x})\gt0$($\lambda=0$)の停留点は、$(x,y)=(0,0)$
- $g({\bf x})=0$($\lambda=-1$)の停留点は、$(x,y)=(-1/2,-1/2)$

