ラグランジュ乗数法
ラグランジュ乗数法とは、複数の変数 ${\bf x}$ に１つ以上の制約条件 $g({\bf x})$ が課せられたときに、関数 $f({\bf x})$ の停留点を求める手法です。
$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({\bf x})+\lambda\nabla g({\bf x})=0 －②$$$$\frac{\partial L}{\partial\lambda}=g({\bf x})=0 －③$$
ラグランジュ関数の意味
２つの条件式②と③のうち、③は制約条件①を表しているので、②について説明します。
制約条件①は $D$ 次元の超曲面であり、関数 $f$ の停留点に対し、この超曲面上の微小変位 ${\bf\delta x}$ を考えます。
$$g({\bf x}+{\bf\delta x})\cong g({\bf x})+{\bf\delta x}\cdot\nabla g({\bf x})$$
${\bf x}$ も ${\bf x}+{\bf\delta x}$ も超曲面 $g$ 上の点であり、$g({\bf x}+{\bf\delta x})=g({\bf x})$ であるため、${\bf\delta x}\cdot\nabla g({\bf x})\cong0$ となります。そして、${\bf\delta x}$ は超曲面 $g({\bf x})$ の接線であるため、$\nabla g({\bf x})$ は超曲面 $g$ に対して垂直であることが分かります。
一方、$f({\bf x})$ についても展開すると、
$$f({\bf x}+{\bf\delta x})\cong f({\bf x})+{\bf\delta x}\cdot\nabla f({\bf x})$$
停留点においては $f({\bf x}+{\bf\delta x})\cong f({\bf x})$ となり、${\bf\delta x}\cdot\nabla f({\bf x})\cong0$ であるため、$\nabla f({\bf x})$ も超平面 $g$ に対して垂直となります。
従って、停留点において $\nabla f({\bf x})$ と $\nabla g({\bf x})$ は平行であり、適当な定数（乗数）$\lambda$ により表すことができるため②が導かれます。
$$\nabla f({\bf x})+\lambda\nabla g({\bf x})=0$$
カルーシュ･クーン･タッカー条件
カルーシュ･クーン･タッカー条件とは、制約条件①（等式制約）の代わりに、次の不等式制約で関数 $f({\bf x})$ を最大または最小にする変数 ${\bf x}$（停留点）を求める場合の制約条件です。
$$g({\bf x})\ge0 －④$$
このとき停留点は、$g({\bf x})\gt0$ の範囲に含まれるか、$g({\bf x})=0$ 上に存在するかの２つのケースに分けることができます。
| ケース | 停留点の場所 | 条件式 | |
| １ | $g({\bf x})\gt0$ | $\nabla f({\bf x})=0$ | $\lambda=0$ |
| ２ | $g({\bf x})=0$ | $\nabla f({\bf x})+\lambda\nabla g({\bf x})$=0 | $\lambda\ne0$ |
ケース１は $g({\bf x})$ の条件は関係なくなりますので、ラグランジュ関数で $\lambda=0$ の場合に等しくなります。ケース２は等式制約で、通常のラグランジュ関数になります。いずれの場合も、次の条件式が成り立つことが分かります。
$$\lambda g({\bf x})=0 －⑤$$
これら④と⑤は、カルーシュ･クーン･タッカー条件と呼ばれています。
簡単な例
２次元の簡単な例で考えます。
$$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$ が導かれます。この２つのケースで停留点を求めると以下のようになります。
- $\lambda=0$ の場合（$g({\bf x})\gt0$）、
停留点は $(x,y)=(0,0)$ であり、$f=1$ となります。 - $\lambda=-1$ の場合（$g({\bf x})=0$）、
停留点は $(x,y)=(-\frac{1}{2},-\frac{1}{2})$ であり、$f=\frac{1}{2}$ となります。
