KKT 条件#

読み: けーけーてぃーじょうけん
英名:

Karush-Kuhn-Tucker 条件の略．

微分可能な関数 \(f \colon \mathbb{R}^n \to \mathbb{R}\)，\(g_i \colon \mathbb{R}^n \to \mathbb{R}\)，\(h_j \colon \mathbb{R}^n \to \mathbb{R}\) に対し，次のような等式・不等式制約をもつ数理計画問題 \((P)\) を考える．

(17)#\[\begin{split}(P) \begin{array}{lll} \min & f(x) & \\ \mathrm{s.t.} & g_i(x) \le 0 & (i=1,\ldots,m) \\ & h_j(x) = 0 & (j=1,\ldots,l) \end{array}\end{split}\]

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

(18)#\[\begin{split}\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,\ldots,l) \\ \bar{\lambda_i} \ge 0,~ g_i(\bar{x}) \le 0,~ \bar{\lambda_i}g_i(\bar{x}) = 0 \ \ (i=1,\ldots,m) \end{array} \right.\end{split}\]

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

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

また，KKT 条件のうち

(19)#\[\bar{\lambda_i} \ge 0,~ g_i(\bar{x}) \le 0,~ \bar{\lambda_i}g_i(\bar{x}) = 0 \ \ (i=1,\ldots,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 条件を満たす局所的最適解が存在することに注意する必要がある．

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