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

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

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

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

$\text{Minimize}f(x)$

$\text{subject to}{g}_i(x)\le 0,h_j(x)=0$

このとき、テンプレート:Mvar が変数、テンプレート:Mvar が目的関数、テンプレート:Math は不等式制約を表す関数、テンプレート:Math は等式制約を表す関数である。不等式制約と等式制約の数はそれぞれ テンプレート:Mvar および テンプレート:Mvar で表す。

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

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

必要条件

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

停留性

For maximizing f(x): $\mathrm{\nabla }f(x^{*})=\sum _{i=1}^m{\mu }_i\mathrm{\nabla }{g}_i(x^{*})+\sum _{j=1}^l{\lambda }_j\mathrm{\nabla }{h}_j(x^{*}),$

For minimizing f(x): $-\mathrm{\nabla }f(x^{*})=\sum _{i=1}^m{\mu }_i\mathrm{\nabla }{g}_i(x^{*})+\sum _{j=1}^l{\lambda }_j\mathrm{\nabla }{h}_j(x^{*}),$

主問題の実行可能条件

$g_i(x^{*})\le 0,\text{ for all }i=1,\dots ,m$

$h_j(x^{*})=0,\text{ for all }j=1,\dots ,l$

双対問題の実行可能条件

${\mu }_i\ge 0,\text{ for all }i=1,\dots ,m$

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

${\mu }_i{g}_i(x^{*})=0,\text{for all}i=1,\dots ,m.$

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

注記：制約条件が「制約想定」と呼ばれる条件を満たしていない場合には、KKT条件から求めた解は必ずしも最適性を満たさないことに注意が必要である． KKT条件が最適性条件となるためには、その制約条件が「Guinard制約想定」と呼ばれる条件を満たしていることが必要十分である(参考：福島,2001年).

関連項目

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

参考文献

• 福島雅夫，「非線形最適化の基礎」，朝倉書店，（2001年4月20日）．ISBN 978-4-254-28001-2。
• テンプレート:Cite book
• 「制約想定を必要としない新しい最適性必要条件の導出」(京都大学、2020年11月09日）