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

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

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

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

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

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

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

必要条件[編集]

目的関数 f: RnR と制約の関数 gi: RnR, hj: RnRx* において連続かつ微分可能であるとする。もし x* が目的関数の極小値を与えるのなら、KKT乗数と呼ばれる μi (i = 1, ..., m), λj (j = 1, ..., l) で以下を満たすものが存在する。

定常性
For maximizing f(x):
For minimizing f(x):
主問題の実行可能条件
双対問題の実行可能条件
スラック変数に関する条件

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

関連項目[編集]

参考文献[編集]

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