KKT条件
等式制約付き最適化問題における1次の最適性
\[
\begin{array}{}
\text{min} \space f(x)\\
\text{s.t.} \space g_i(x) = 0, \space i = 0, \dots , m\\
x \in \mathbb{R}^n
\end{array}
\]
上記の最適問題において1次の最適性は以下
点\(x^*\)は局所最適解かつ正則。この時以下を満たす\(u^*\)が存在する
\[
\nabla f(x^*) + \Sigma_{i=1}^{m} u_i^* \nabla g_i(x^*) = 0
\]
Note
点\(x\)において\(\nabla g_1(x), \dots ,\nabla g_m(x)\)が互いに1次独立ならば点\(x\)は正則であるという
不等式制約付き最適化問題における1次の最適性
\[
\begin{array}{}
\text{\rm min} \space f(x)\\
\text{s.t.} \space g_i(x) \leq 0, \space i = 0, \dots , m\\
x \in \mathbb{R}^n
\end{array}
\]
上記の最適問題において1次の最適性は以下
点\(x^*\)は局所最適解かつ正則。この時以下を満たす\(u^*\)が存在する
\[
\begin{array}{}
\nabla f(x^*) + \Sigma_{i=1}^{m} u_i^* \nabla g_i(x^*) = 0\\
u_i^* g_i(x^*) = 0, \space i = 0, \dots , m\\
u_i^* \geq 0, \space i = 0, \dots , m
\end{array}
\]
2式目は相補性条件と呼ばれる。\(g_i(x^*)\)が有効な時は\(g_i(x^*)=0\)となり, 有効でない場合は\(u_i^*=0\)となる。