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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

カルーシュ・キューン・タッカー条件 (英: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 が目的関数、gi (i = 1, 2, ... , m) は不等式制約を表す関数、hj (j = 1, 2, ... , l) は等式制約を表す関数である。不等式制約と等式制約の数はそれぞれmおよびlで表す。

この際、KKT条件が与えられるためには正規条件と呼ばれるいくつかの条件のうちの1つを満たす必要がある。一例として、f凸関数で、かつgiおよびhjアフィン関数であるなどの条件がある.

必要条件[編集]

目的関数f: RnRと制約の関数gi: RnRhj: RnRx*において連続かつ微分可能であるとする。もし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^*) \le 0, \mbox{ for all } i = 1, \ldots, m
h_j(x^*) = 0, \mbox{ for all } j = 1, \ldots, l \,\!
双対問題の実行可能条件
\mu_i \ge 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条件を同様に定めることができる。

関連項目[編集]

参考文献[編集]

  • 田村 明久, 村松 正和 (2002), 最適化法, 共立出版, ISBN 4-320-01616-5