KKT条件

HOME>>メモ>>アルゴリズム>>SVM>>KKT条件

Karush-Kuhn-Tucker条件

不等式制約条件を持つ関数最適化問題で極小値がとらなければならない条件です。

$n$次元のベクトル$\bm x=(x_1, x_2, \cdots, x_n)$に関する最適化問題を考えます。 \[\min_{\bm x} f(\bm x)\] ただし、次の不等式制約条件を持つものとします。 \[g_1(\bm x) \le 0, g_2(\bm x) \le 0,\cdots,g_m(\bm x) \le 0\] \[h_1(\bm x) = 0, h_2(\bm x) = 0,\cdots,h_l(\bm x) = 0\]

この問題を双対な問題に置き換えます。ラグランジュ乗数$\lambda_i, \mu_j$を導入し、ラグランジュ関数を \[L(\bm x,\bm \lambda,\bm \mu)=f(\bm x)+\sum_{i=1}^n \lambda_i g_i(\bm x)+\sum_{j=1}^l \mu_j h_j(\bm x)\] と定義します。

このとき極小値$\bm x^*$は次の条件を満たさなければなりません。 \[\nabla_{\bm x}L(\bm x^*,\bm \lambda,\bm \mu)=\nabla f(\bm x^*)+\sum_{i=1}^n \lambda_i\nabla g_i(\bm x^*)+\sum_{j=1}^l \mu_j\nabla h_j(\bm x^*)=\bm 0\] \[g_i(\bm x^*) \le 0, \lambda_i \ge 0, \lambda_i g_i(\bm x^*)=0 (i=1,2,\cdots,m)\] \[h_1(\bm x) = 0, h_2(\bm x) = 0,\cdots,h_l(\bm x) = 0\]

この中で、$\lambda_i g_i(\bm x^*)=0$は相補性条件と言います。

参考