概要
機械学習について学習する中で出てきた，ラグランジュの未定乗数法とKKT問題をまとめ，自分なりに納得するために説明を付けました(厳密な証明を書くのは僕の数学力では無理があるので)．
またここでは，簡単化のために2変数関数を考えることにします．
制約なし最適化問題
$$
\begin{array}{ll}
minimize & f(x, y)
\end{array}
$$
解法
$f$を各変数で偏微分して解を絞り込む(あくまで必要条件であることに注意)．
$(a, b)$が$f$を最小化する必要条件は以下の通り．
$$
\nabla f(a, b) = 0
$$
等式制約付き最適化問題
$$
\begin{array}{ll}
minimize & f(x, y) \\
subject~to & g(x, y) = 0
\end{array}
$$
解法
ラグランジュの未定乗数法を利用して解を絞り込む．
まず$g_y \neq 0$を仮定しておく．
この仮定の下で，$(a, b)$が$f$を最小化する必要条件は以下の通り．
$$
L(x, y, \lambda) := f(x, y) - \lambda g(x, y)
$$
として，$(a, b)$が以下の方程式の解．
$$
\frac{\partial L}{\partial x} = \frac{\partial L}{\partial y} = 0 \\
\frac{\partial L}{\partial \lambda} = 0 ~ (\Leftrightarrow g(x, y) = 0)
$$
説明
制約条件$g(x, y) = 0$を$y$に関して解くことは一般にはできない．
しかし，$g_y \neq 0$を満たすならば$(a, b)$の近傍では$y$に関して一意に解ける(陰関数の存在定理)．
$(a, b)$の近傍で$g(x, y) = 0$を$y$に関して$y = \phi(x)$と解くと，$(a, b) = (a, \phi(a))$で$f(x, \phi(x))$は最小値を取るので，
$$
\begin{array}{lll}
\frac{d}{dx} f(x, \phi(x)) & = & f_x + f_y \frac{d\phi}{dx} \\
& = & 0
\end{array}
$$
また，$g(x, \phi(x))$は恒等的に0なので，
$$
\begin{array}{lll}
\frac{d}{dx} g(x, \phi(x)) & = & g_x + g_y \frac{d\phi}{dx} \\
& = & 0
\end{array}
$$
以上から，
$$
\frac{d\phi}{dx} = -\frac{f_x}{f_y} = -\frac{g_x}{g_y} \\
\frac{f_y}{g_y} = \frac{f_x}{g_x} =: \lambda
$$
とすれば，
$$
\frac{d}{dx} f(x, \phi(x)) = f_x - \lambda g_x = 0 \\
-\frac{\lambda}{\phi^\prime} \frac{d}{dx} f(x, \phi(x)) = f_y - \lambda g_y = 0
$$
したがって，$g(x, y) = 0$と合わせて，
$$
\frac{\partial L}{\partial x} = \frac{\partial L}{\partial y} = \frac{\partial L}{\partial \lambda} = 0
$$
不等式制約付き最適化問題
$$
\begin{array}{ll}
minimize & f(x, y) \\
subject~to & g(x, y) \leq 0
\end{array}
$$
解法
KKT条件を利用して解を絞り込む．
$f(x, y)$が凸関数であることを仮定して，$(a, b)$が$f$を最小化する必要条件は以下の通り．
$$
L(x, y, \lambda) := f(x, y) - \lambda g(x, y)
$$
として，$(a, b)$が以下の方程式の解．
$$
\frac{\partial L}{\partial x} = \frac{\partial L}{\partial y} = 0 \\
g(x, y) \leq 0 \\
\lambda g(x, y) = 0 \\
\lambda \leq 0 \\
$$
説明
制約条件が不等式である場合，$f(x, y)$の真の最小値が$g(x, y) \leq 0$の領域内にあるか，領域外にあるかが問題になる．
-
$f(x, y)$の真の最小値が$g(x, y) \leq 0$の領域内にある場合
求める答えは制約条件に関係なく，真の最小値とすればよい．
したがって，ラグランジュの未定乗数法で，$\lambda = 0$とすればよい．
$$
L(x, y, \lambda) := f(x, y) - 0 \cdot g(x, y)
$$ -
$f(x, y)$の真の最小値が$g(x, y) \leq 0$の領域外にある場合
$f$が凸関数ならば，制約条件を満たしながら$f(x, y)$を最小化する解は$g(x, y) = 0$の境界上に存在する．したがって，ラグランジュの未定乗数法を利用して解くことができる．
$$
L(x, y, \lambda) := f(x, y) - \lambda g(x, y) \\
\frac{\partial L}{\partial x} = \frac{\partial L}{\partial y} = \frac{\partial L}{\partial \lambda} = 0
$$
以上から，ラグランジュの未定乗数法を利用でき，また，$\lambda = 0$または$g(x, y) = 0$のいずれかが成立するので，$\lambda g(x, y) = 0$と表せる．
更に，$\lambda \neq 0$の場合，つまり真の最適解が制約条件の領域外にある場合，$\lambda$の符号についても言える．
ラグランジュの未定乗数法より，$f(x, y)$の勾配と$g(x, y)$の勾配は平行であった．
$$
\nabla f(x, y) = \lambda \nabla g(x, y)
$$
ここで，制約条件の不等号の向きと，最小化か最大化かという，計4パターンでの$\lambda$の符号を考える．
-
$g(x, y) \leq 0$，最小化(今回のパターン)
制約条件の不等号の向きより，$g(x, y)$の値は制約条件を満たす領域の内側から外側に向かって増大する．
したがって，$\nabla g(x, y)$は領域の外側に向かうベクトル．
一方，$f(x, y)$を最小化する点は制約条件の領域外に存在するので，$f(x, y)$は領域の外側から内側に向かって増大する．
したがって，$\nabla f(x, y)$は領域の内側へ向かうベクトル．
以上より，$\nabla g(x, y)$と$\nabla f(x, y)$は反対向きのベクトルなので，$\lambda < 0$． -
$g(x, y) \geq 0$，最大化
同様に，$g(x, y)$は外側に向かって増大，$f(x, y)$は外側に向かって増大．
したがって，$\nabla g(x, y)$と$\nabla f(x, y)$は同じ向きのベクトルで，$\lambda > 0$． -
$g(x, y) \leq 0$，最小化
$g(x, y)$は内側に向かって増大，$f(x, y)$は内側に向かって増大．
したがって，$\nabla g(x, y)$と$\nabla f(x, y)$は同じ向きのベクトルで，$\lambda > 0$． -
$g(x, y) \geq 0$，最大化
$g(x, y)$は内側に向かって増大，$f(x, y)$は外側に向かって増大．
したがって，$\nabla g(x, y)$と$\nabla f(x, y)$は反対向きのベクトルで，$\lambda < 0$．
4つのパターンにおける$\lambda$の符号は，$f(x, y)$や$g(x, y)$を必要に応じてマイナス倍し，$-g(x, y) \leq 0$，$-f(x, y)$の最小化問題に帰着することでも確かめられる．
複数の制約条件がある場合
$$
\begin{array}{lll}
minimize & f(x, y) \\
subject~to & g_i(x, y) = 0 & (1 \leq i \leq n) \\
& h_i(x, y) \leq 0 & (1 \leq i \leq m)
\end{array}
$$
解法
これまでの方法を全て合併するような方法で解を絞り込む．
$f(x, y)$が凸関数であることを仮定して，$(a, b)$が$f$を最小化する必要条件は以下の通り．
$$
L(x, y, \lambda) := f(x, y) - \sum_{i = 1}^{n} \lambda_i g_i(x, y) - \sum_{i = 1}^{m} \mu_i h_i(x, y)
$$
として，$(a, b)$が以下の方程式の解．
$$
\frac{\partial L}{\partial x} = \frac{\partial L}{\partial y} = \frac{\partial L}{\partial \lambda_i} = 0 \\
h_i(x, y) \leq 0 \\
\mu_i h_i(x, y) = 0 \\
\mu_i \leq 0 ~~~ \forall i
$$
これは，最適化問題に一つずつ制約条件を課していくことを考えれば納得できる．