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

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

カルーシュ・クーン・タッカー条件（英: Karush-Kuhn-Tucker condition）、略してKKT条件とは、数理最適化、特に非線形計画問題において、局所最適解が満たす必要条件です。この条件は、対象となる関数の微分に基づいて記述されます。

概要

KKT条件は、目的関数を最小化または最大化する際に、変数に対する制約条件（特に不等式制約）が存在する場合に非常に有用です。等式制約のみを扱うラグランジュの未定乗数法を一般化・拡張したものであり、現実世界の様々な最適化問題で頻繁に登場する不等式制約を適切に扱える点が大きな特徴です。

これらの条件は連立方程式として表現されますが、一般の非線形問題の場合、この連立方程式を解析的な閉形式で直接解くことは困難です。そのため、通常は反復計算に基づく数値解法が用いられます。効率的な数値解法は数多く研究されており、それらが広く利用されています。

歴史的には、カルーシュの研究が後になって広く認識されたため、以前はクーン・タッカー条件（KT条件）と呼ばれることもありました。

対象となる問題

KKT条件は、以下のような標準的な形式の非線形計画問題に適用されます。

目的関数 $f(x)$ を最小化する $x$ を見つける。

$\qquad \min_{x \in \mathbb{R}^n} f(x)$

制約条件として以下を満たす必要がある。

$\qquad g_i(x) \le 0, \quad \text{for } i=1, \ldots, m$
$\qquad h_j(x) = 0, \quad \text{for } j=1, \ldots, l$

ここで、$x$ は最適化の対象となる変数ベクトル、$f(x)$ は目的関数です。$g_i(x)$ は $m$ 個の不等式制約関数、$h_j(x)$ は $l$ 個の等式制約関数を表します。

KKT条件

目的関数 $f$ および制約関数 $g_i, h_j$ が、局所最適解となりうる点 $x^$ において連続かつ微分可能であると仮定します。もし $x^$ がこの問題の局所最適解であれば、KKT乗数と呼ばれる $\mu_i \,(i=1,\ldots,m)$ および $\lambda_j \,(j=1,\ldots,l)$ が存在し、以下の条件群を満たします。

1. 停留性 (Stationarity):
$x^$ における目的関数の勾配 $
abla f(x^)$ が、制約関数の勾配 $
abla g_i(x^)$ および $
abla h_j(x^)$ の線形結合として表されます。最小化問題の場合、以下の式が成り立ちます。

$\qquad -
abla f(x^) = \sum_{i=1}^{m} \mu_i
abla g_i(x^) + \sum_{j=1}^{l} \lambda_j
abla h_j(x^)$

（最大化問題の場合は $
abla f(x^)$ となります。）

2. 主問題の実行可能条件 (Primal Feasibility):
点 $x^$ は元の非線形計画問題の制約条件を満たす必要があります。

$\qquad g_i(x^) \le 0, \quad \text{for } i=1, \ldots, m$
$\qquad h_j(x^) = 0, \quad \text{for } j=1, \ldots, l$

3. 双対問題の実行可能条件 (Dual Feasibility):
不等式制約に対応するKKT乗数 $\mu_i$ には非負の制約があります。

$\qquad \mu_i \ge 0, \quad \text{for } i=1, \ldots, m$

（等式制約に対応する $\lambda_j$ には一般に符号の制約はありません。）

4. 相補性条件 (Complementary Slackness):
不等式制約 $g_i(x) \le 0$ と、それに対応するKKT乗数 $\mu_i$ との間には特別な関係があります。

$\qquad \mu_i g_i(x^) = 0, \quad \text{for } i=1, \ldots, m$

この条件は、もしある不等式制約 $g_i(x^) \le 0$ が最適解 $x^$ で厳密な不等式 $g_i(x^) < 0$ であるならば、対応するKKT乗数 $\mu_i$ はゼロでなければならないことを意味します。逆に、$\mu_i > 0$ であるならば、その制約は $g_i(x^) = 0$ でなければなりません。

必要条件と制約想定

KKT条件は、局所最適解であるための「必要条件」です。KKT条件を満たす点が必ずしも局所最適解であるとは限りません。最適性を保証するには追加の条件が必要です。

また、KKT条件が局所最適解の必要条件として機能するためには、「正規条件」（制約想定、Constraint Qualification）と呼ばれる満たすべき条件が存在します。これは、制約条件が非病的な振る舞いをすることを保証します。例えば、制約関数がすべてアフィン関数である場合などが正規条件を満たします。Guinard制約想定などがより一般的な条件として知られています。

特殊ケースと応用

不等式制約が存在しない問題の場合、KKT条件は等式制約のみを持つ最適化問題に対するラグランジュの未定乗数法と完全に一致します。

KKT条件は、線形計画法などの多くの最適化手法や問題の理論的基盤として重要です。特に、線形計画問題に対する主双対内点法のようなアルゴリズムで中心的な役割を果たします。

関数が微分可能でない場合には、劣微分を用いたKKT条件の概念が定義されます。

関連分野

線型計画問題、半正定値計画問題、二次錐計画問題、双対問題など。

参考文献

福島雅夫『非線形最適化の基礎』、田村明久, 村松正和『最適化法』

もう一度検索