トップ > 数理計画用語集 > KKT 条件

数理計画用語集

KKT 条件

読み:けーけーてぃーじょうけん
関連制約想定

Karush-Kuhn-Tucker 条件の略.微分可能な関数 $f:\mathbb{R}^n \rightarrow \mathbb{R}$,$g_i:\mathbb{R}^n \rightarrow \mathbb{R}$,$h_j:\mathbb{R}^n \rightarrow \mathbb{R}$ に対し,次のような等式・不等式制約をもつ数理計画問題(P)を考える.

(P) $\begin{array}{lll} \min & f(x) & \\ \mathrm{s.t.} & g_i(x) \le 0 & (i=1,\dots,m) \\ & h_j(x) = 0 & (j=1,\dots,l) \end{array}$

以下の (*) 式が問題(P)に対する KKT 条件である.

$ \left\{ \begin{array}{l} \nabla f(\bar{x}) + \displaystyle\sum_{i=1}^m{\bar{\lambda_i} \nabla g_i(\bar{x})} + \displaystyle\sum_{j=1}^l{\bar{\mu_j} \nabla h_j(\bar{x})} = 0 \\ h_j(\bar{x}) = 0 \ \ (j=1,\dots,l) \\ \bar{\lambda_i} \ge 0,~ g_i(\bar{x}) \le 0,~ \bar{\lambda_i}g_i(\bar{x}) = 0 \ \ (i=1,\dots,m) \end{array} \right. $ -(*)

(*) 式の $\bar{x}$ に対し,制約想定を仮定したとき,KKT 条件(*)を満たすような $\bar{\lambda_i}$,$\bar{\mu_j}$ の存在が保証され,$\bar{x}$ が問題(P)の局所的最適解となることの 1 次の必要条件となる.

ちなみに,この条件は Kuhn と Tucker による論文で示されたが,後に Karush が等価な条件を示していたことが判明したため,Karush-Kuhn-Tucker 条件または KKT 条件と呼ばれている.

また,(*) 式のうちの

\[ \bar{\lambda_i} \ge 0,~ g_i(\bar{x}) \le 0,~ \bar{\lambda_i}g_i(\bar{x}) = 0 \ \ (i=1,\dots,m) \]

は,各 $i$ について $\bar{\lambda_i}$,$g_i(\bar{x})$ の少なくとも一方が 0 となることを意味しており,一般に相補性条件と呼ばれている.

線形計画問題の場合,相補性条件は KKT 条件において唯一の非線形な式となるが,単体法は探索範囲を基底解に限定することで,相補性を陽に考慮することなく解を求めていると解釈できる.内点法では相補性条件の右辺にパラメータ $\mu$ を置いて KKT 条件を変形,$\bar{\lambda_i}$,$-g_i(\bar{x})$ を正になるように制約しつつ,変形した KKT 条件を非線形方程式系として解くことを繰り返し,$\mu$ を調整することで KKT 条件の解を求める.

実務的には線形計画問題凸計画問題においては KKT 条件は最適性の必要十分条件であるが,解は一意とは限らないこと,一般の非線形計画問題には KKT 条件を満たす局所的最適解が存在することに注意する必要がある.

Numerical Optimizer に組み込まれている信頼領域アルゴリズム[2]は局所的最適解への大域的収束と超一次収束を示しているが,常に大域的最適解を求めることを保証するものではない.

[参考]
[1] 福島雅夫, 非線形最適化の基礎, 朝倉書店, 2001
[2] H. Yamashita, H. Yabe, and T. Tanabe,A globally and superlinearly convergent primal-dual interior point trust region method for large scale constrained optimization, Mathematical Programming Ser.B,January 2005, Vol.102, Number 1, pp.111-151 (2005)