PROFILPELAJAR.COM

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

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

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

{\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$ がアフィン関数であるなどの条件がある．

（なお、不等式制約条件 $\;g_{i}(x)\leq 0\;$ は無制約のスラック変数 $s_{i}$ を用いることで、等式制約条件 $\;g_{i}(x)+s_{i}^{2}=0$ に置きかえて扱うこともできる.）

必要条件

目的関数 $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^{*}),$