KKT条件の導出

$A = [A,B,-B], x = [u,v_+,v_-]^T, v =v_+ -v_-, b=-c$とおく。Farkasの補題より系１が求まる。

許容方向$s$が存在すると仮定する。$x^*$が局所最適解であるとする。

不等式制約について、

\begin{eqnarray} g_i(x^*+ \alpha s) = g_i(x^*)+\alpha \nabla g_i(x^*)^Ts +o(\alpha) \end{eqnarray}

十分小さい$\alpha$では$g_i(x^*+\alpha s)<0$であり、不等式制約を満たすことがわかる。

等式制約について

\begin{eqnarray} h_j(x^*+\alpha s) = h_j(x^*)+\alpha \nabla h_j(x^*)^Ts +o(\alpha) \end{eqnarray}

十分小さい$\alpha$では$h_j(x^*+\alpha s)=0$であり、等式制約を満たすことがわかる。

$x^{*}$は局所最適解であるので、十分小さい$\alpha$では下式が成り立つ。

\begin{eqnarray} f(x^*+\alpha s)=f(x^*)+\alpha f(x^*)^Ts\geq f(x^*) \end{eqnarray}

しかし、$\nabla f(x^*)^Ts < 0$なので矛盾する。よって、$s$は存在しない。

$x^{*}$が局所最適解ならば式7を満たすベクトル$s$は存在しない。

\begin{eqnarray} \nabla f(x)^Ts < 0 \\ \nabla g_i(x)^Ts < 0　,i \in I(x) \tag{7} \end{eqnarray}

式7より、$Ax>0$を満たす$x$は存在しない。
ただし、

\begin{eqnarray} A = \left( \begin{array}{ccc} -\nabla f(x)^T & \\ -\nabla g_1(x)^T &\\ \vdots &\\ -\nabla g_k(x)^T \end{array} \right) \end{eqnarray}

Gordanの二者択一定理(1)が成り立たないので(2)が成り立つ。つまり、$A^Ty = 0$、$y \geq 0$、$y \neq 0$を満たす$y$が存在する。

\begin{eqnarray} A^Ty = \left(-\nabla f(x),-\nabla g_1(x),\cdots ,-\nabla g_k(x)\right)\left( \begin{array}{ccc} y_0 \\ y_1 \\ \vdots \\ y_k \end{array} \right)\\ = -y_0 \nabla f(x) - y_1 \nabla g_1(x) \cdots - y_k \nabla g_k(x) = 0 \end{eqnarray}

まとめると、

\begin{eqnarray} y_0 \nabla f(x) + \sum_{i \in I(x)}y_i \nabla g_i(x) = 0 \end{eqnarray}

$i \notin I(x)$のとき、$y_i = 0$とおけば、$y_i \nabla g_i(x) = 0$、$y_i g_i(x) = 0$である。
$i \in I(x)$のとき$g_i(x)=0$なので$y_i g_i(x) = 0$である。

不等式制約$g_i(x) \leq 0$を満たす必要があることを思い出せば、Fritz Johnの定理を得る。

\begin{eqnarray} &y_0 \nabla f(x) +\sum_{i=1}^{l}y_i\nabla g_i(x) = 0,\\ &g_i(x) \leq 0,\\ &y_i \leq 0, \\ &y_i g_i(x) = 0. \end{eqnarray}

線形独立制約を想定する。Fritz Johnの定理より$y_0=0$と仮定すると、線形独立制約想定より$y_i=0$となり矛盾する。よって、$y_0 > 0$である。$y_i = y_i /y_0$と改めて書き直せばKKT条件をえる。

\begin{eqnarray} &\nabla f(x) + \sum_{i=1}^m y_i &\nabla g_i(x)=0,\\ &g_i(x) \leq 0,\\ &y_i \geq 0,　　　 \\ &y_i g_i (x) = 0 \end{eqnarray}