KKT条件 · Beki Kaneko

KKT条件

2020-03-17

KKT条件 (Karush-Kuhn-Tucker conditions)とは、非線形計画問題における最適性の1次の必要条件です。

非線形計画問題

$\begin{align*} \min f(x) &\\ {\rm subject\ to\ } h_i(x) &= 0 , i = 1, \cdots, m\\ g_j(x) &\leq 0, j = 1, \cdots ,r \end{align*}$

の局所最小解 $x^*$ に対して、KKT条件

$\begin{align*} &\nabla f(x^*) + \sum_{i} \lambda_i \nabla h_i(x^*) + \sum_j \mu_j \nabla g_j (x^*) = 0\\ &h(x^*) = 0\\ &g_j(x^*) \leq 0 ,\ \mu_j \geq 0 ,\ \mu_j g_j(x^*) = 0,\ j = 1, \cdots r \end{align*}$

を満たす $\lambda \in R^m$ と $\mu \in R^r$ が存在します。

応用する上でより重要なのは次の性質です。

定理 $f$ と $g_j,\ j = 1, \cdots, r$ は凸関数であり、 $h_i, i = i,\ \cdots, m$ は1次関数であるとする。このとき、 $(x^*, \lambda^*, \mu^*)$ がKKT点であれば、 $x^*$ は非線形計画問題の大域的最小解である。

これは、凸関数の性質 $f(x) \geq f(x^*) + \delta f(x^*)^T (x-x^*)$ とKKT条件を組み合わせることで、 $f(x) \geq f(x^*)$ が成り立つことを示すことで証明できます。

KKT条件は、等式制約のみの問題に対しては、ラグランジュの未定乗数法と一致します。このため、KKT条件はラグランジュの未定乗数法の一般化と考えることもできます。

例題 : エントロピー最大化
エントロピーが最大となる $n$ 個の元をもつ確率分布を求める問題は、次のように定式化できます。

$\begin{align*} & \max - \sum_{i=1}^n p_i \ln p_i\\ {\rm subject\ to\ } & \sum_{i=1}^n p_i =1\\ & p_i \geq 0,\ i = 1, \cdots, n \end{align*}$

これはKKT条件を用いて解けます。

$\begin{align*} f(p) &= \sum_{i=1}^n p_i \ln p_i\\ h(p) &= \sum_{i=1}^n p_i-1 \\ g_i (p) &= - p_i \leq 0 \end{align*}$

とおくと、

$\begin{align*} \delta_i f(p_i)& = \ln p_i + 1\\ \delta_i h(x) &= 1\\ \delta_i g_j(x) &= -\delta_{ij} \end{align*}$

なので、KKT条件は

$\begin{align*} \left(\begin{array}{c} \ln p_1 + 1 \\ \vdots\\ \ln p_n + 1 \end{array}\right) + \lambda \left(\begin{array}{c} 1\\ \vdots\\ 1 \end{array}\right) + \left(\begin{array}{c} \mu_1 \\ \vdots \\ \mu_n \end{array}\right) = 0 \\ \sum_{i=1}^n p_i - 1 = 0, \ - p_i \leq 0 , \ -p_i \mu_i = 0 \end{align*}$

とかけます。 $p_i = 0$ とすると $\ln p_i = \infty$ となってしまい、第１式を満たすことができなくなってしまいます。そこですべての $i$ に対して $p_i > 0$ とすると、 $\mu_i = 0$ となるので、

$p_i = e^{-\lambda -1}$

が成り立ちます。さらに第2条件から解 $p = (1/n, \cdots, 1/n)^T$ が得られます。

参考文献

山下信雄, 非線形計画法, 朝倉書店 (2015)