カルーシュ・クーン・タッカー条件

カルーシュ・クーン・タッカー条件（英: Karush-Kuhn-Tucker condition）あるいはKKT条件とは、非線形計画において一階導関数が満たすべき最適条件を指す。ラグランジュの未定乗数法が等式制約のみを扱うのに対して、KKT条件を用いた解法は不等式制約も扱うことができる。KKT条件に対応する連立方程式は、解析的に閉形式解法が導かれる特殊な場合を除いては直接的には解かない。すでにKKT条件の連立方程式を数値的に解く方法は数多く確立されており、それらを用いて解くのが一般的である。KKT条件は線形計画法における主双対内点法などの解法において、重要な役割を持つ。

対象となる非線形計画問題編集

次のような非線形計画問題を考える。

{\text{Minimize}}\;f(x)

{\text{subject to}}\;g_{i}(x)\leq 0,\;h_{j}(x)=0

このとき、 $x$ が変数、 $f$ が目的関数、 $g i (i = 1, 2, ... , m)$ は不等式制約を表す関数、 $h j (j = 1, 2, ... , l)$ は等式制約を表す関数である。不等式制約と等式制約の数はそれぞれ $m$ および $l$ で表す。

この際、KKT条件が局所値の必要条件となるためには、正規条件と呼ばれるいくつかの条件のうちの1つを満たす必要がある。一例として、 $f$ が凸関数で、かつ $g i$ および $h j$ がアフィン関数であるなどの条件がある．

必要条件編集

目的関数 $f\colon \mathbb {R} ^{n}\to \mathbb {R}$ と制約の関数 $g_{i}\colon \mathbb {R} ^{n}\to \mathbb {R} ,\,h_{j}\colon \mathbb {R} ^{n}\to \mathbb {R}$ が $x^{*}$ において連続かつ微分可能であるとする。もし $x^{*}$ が目的関数の極小値を与えるのなら、KKT乗数と呼ばれる $\mu _{i}(i=1,\dots ,m),\lambda _{j}(j=1,\dots ,l)$ で以下を満たすものが存在する。

停留性: For maximizing f(x): $\nabla f(x^{*})=\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}\nabla h_{j}(x^{*}),$; For minimizing f(x): $-\nabla f(x^{*})=\sum _{i=1}^{m}\mu _{i}\nabla g_{i}(x^{*})+\sum _{j=1}^{l}\lambda _{j}\nabla h_{j}(x^{*}),$