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

カルーシュ・クーン・タッカー条件（英: 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: Rⁿ ↦ R と制約の関数 g_i: Rⁿ ↦ R, h_j: Rⁿ ↦ R が x^* において連続かつ微分可能であるとする。もし x^* が目的関数の極小値を与えるのなら、KKT乗数と呼ばれる μ_i (i = 1, ..., m), λ_j (j = 1, ..., 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^{*}),$

主問題の実行可能条件

$g_{i}(x^{*})\leq 0,{\mbox{ for all }}i=1,\ldots ,m$

$h_{j}(x^{*})=0,{\mbox{ for all }}j=1,\ldots ,l\,\!$

双対問題の実行可能条件

$\mu _{i}\geq 0,{\mbox{ for all }}i=1,\ldots ,m$

スラック変数に関する条件

$\mu _{i}g_{i}(x^{*})=0,{\mbox{for all}}\;i=1,\ldots ,m.$

特に m = 0 の場合は等式制約のみを持つ問題となるので、KKT条件はラグランジュの未定乗数が満たすべき条件と同値になり、KKT乗数はラグランジュ乗数と呼ばれる。仮に、いくつかの関数が微分不可能である場合、劣微分を用いたKKT条件を同様に定めることができる。

関連項目

• 線型計画問題
• 半正定値計画問題
• 二次錐計画問題
• 双対問題

参考文献

• 田村, 明久、村松, 正和『最適化法』共立出版〈工系数学講座 17〉、2002年4月1日。ISBN 4-320-01616-5。