KKT Conditionsのざっくりとした導出

等式の束縛条件を持つ問題のDuality

束縛条件 $u_i(\mathbf{x})=0\,\,(i=1,...,m)$ の下に $f(\mathbf{x})$ の停留値を求める問題は、一般に、Lagrangeの未定乗数法により、

$L(\mathbf{x},\mathbf{a})\, := f(\mathbf{x})+\sum_i{a_iu_i(\mathbf{x})}$ ---- (1-1)

の停留値問題に帰着される。つまり、

$\frac{\partial L}{\partial \mathbf{x}} = 0 , \,\frac{\partial L}{\partial \mathbf{a}} = 0$

の解を求めると、 $L(\mathbf{x},\mathbf{a})$ の（束縛条件の無い）停留値と $f(\mathbf{x})$ の（束縛条件のある）停留値が一致する。

ここで、 $\mathbf{a}$ を固定して、 $\mathbf{x}$ についての停留値 $\mathbf{\tilde{x}}(\mathbf{a})$ を先に求めて、 $L$ に再代入したものをdual function $\tilde{L}$ として定義する。

$\tilde{L}(\mathbf{a})\, := L(\mathbf{\tilde{x}}(\mathbf{a}),\mathbf{a})$

$\frac{\partial L}{\partial \mathbf{x}}|_{\mathbf{x}=\mathbf{\tilde{x}}(\mathbf{a})} = 0$

この時、dual functionの停留値を求めることと、元々のLangrangeanの停留値を求めることは同じになる。なぜなら、

$\frac{d\tilde{L}}{d\mathbf{a}}=\frac{\partial L}{\partial \mathbf{x}}|_{\mathbf{x}=\mathbf{\tilde{x}}(\mathbf{a})}\frac{d\mathbf{\tilde{x}}}{d\mathbf{a}}+\frac{\partial L}{\partial \mathbf{a}}=\frac{\partial L}{\partial \mathbf{a}}$

より、

$\frac{d\tilde{L}}{d\mathbf{a}}=0 \Leftrightarrow \frac{\partial L}{\partial \mathbf{a}}=0$

つまり、(1-1)の（束縛条件を持たない）停留値問題の解を $\mathbf{x^*},\,\mathbf{a^*}$ として、次の関係(Strong Duality)が成り立つ。

・ $f(\mathbf{x^*}) = L(\tilde{\mathbf{x}}(\mathbf{a^*}), \mathbf{a^*}) = \tilde{L}(\mathbf{a^*})$ ----- (1-2)

・ $\mathbf{x^*} = \tilde{\mathbf{x}}(\mathbf{a^*})$ は、元々の（束縛条件を持つ）停留値問題の解でもある。

・ $\mathbf{a^*}$ は、dual function $\tilde{L}(\mathbf{a})$ の停留値問題の解でもある。

不等式の束縛条件を持つ問題のDuality

束縛条件 $h_i(\mathbf{x}) \ge 0\,\,(i=1,...,m)$ の下に $f(\mathbf{x})$ の最小値を求める問題を考える。

$\mathbf{x^*} = \arg\min_{\mathbf{x}}f(\mathbf{x})$

$f(\mathbf{x^*})=\min_{\mathbf{x}}f(\mathbf{x})$

まず、形式的に次のLagrangeanを定義する。

$L(\mathbf{x},\mathbf{a})\, := f(\mathbf{x})-\sum_i{a_ih_i(\mathbf{x})}$

これが、 $\mathbf{x}$ について下に凸で最小値を持つ範囲の $\mathbf{a}$ に対して、次のようにdual functionを定義する。

$\tilde{L}(\mathbf{a})\, := \min_{\mathbf{x}}L(\mathbf{x},\mathbf{a}) = L(\mathbf{\tilde{x}}(\mathbf{a}),\mathbf{a})$

$\frac{\partial L}{\partial \mathbf{x}}|_{\mathbf{x}=\mathbf{\tilde{x}}(\mathbf{a})} = 0$

この時、任意の $a_i \ge 0$ に対して次の不等式が成り立つ。

$f(\mathbf{x^*}) \ge L(\mathbf{x^*},\mathbf{a}) \ge \tilde{L}(\mathbf{a})$ ---- (2-1)

（ $\mathbf{x^*}$ は、束縛条件下の最小値問題の解なので、 $h_i(\mathbf{x^*}) \ge 0$ ）

従って、仮に、

$f(\mathbf{x^*}) = \tilde{L}(\mathbf{a})$ ---- (2-2)

を満たす $a_i \ge 0$ が存在する場合、もともとの最小値問題の解は、次の最大値問題を解くことに帰着する。

$\mathbf{a^*} = \arg\max_{\mathbf{a}}\tilde{L}(\mathbf{a})$

この $\mathbf{a^*}$ は、(2-1)の不等式をすべて等式にするので、

$f(\mathbf{x^*}) = L(\mathbf{x^*},\mathbf{a^*}) = \tilde{L}(\mathbf{a^*}) = L(\mathbf{\tilde{x}(\mathbf{a^*})},\mathbf{a^*})$

つまり、

$f(\mathbf{x^*}) = L(\mathbf{x^*},\mathbf{a^*}) = L(\mathbf{\tilde{x}(\mathbf{a^*})},\mathbf{a^*}) = \min_{\mathbf{x}}L(\mathbf{x},\mathbf{a^*})$

これから、次も成り立つことが分かる。

$f(\mathbf{x^*}) = \tilde{L}(\mathbf{a^*}) , \, \mathbf{x^*} = \mathbf{\tilde{x}}(\mathbf{a^*})$

ここで、(2-2)を満たす $a_i$ の存在を示す。

元々の条件付き最小値問題の解 $\mathbf{x^*}$ は、束縛条件を満たす領域に存在するが、束縛条件は次の2つに分類される。

$h_i(\mathbf{x^*}) = 0$ : Activeな束縛条件

$h_i(\mathbf{x^*}) > 0$ : Inactiveな束縛条件

Inactiveな束縛条件は、 $\mathbf{x^*}$ の近傍では、 $\mathbf{x}$ を束縛しないことに注意すると、Inactiveな束縛条件に対して $a_i = 0$ とおいた、

$L(\mathbf{x},\mathbf{a})\, := f(\mathbf{x}) - \sum_{i:Active}{a_ih_i(\mathbf{x})}$

の停留値問題の解として、 $\mathbf{x^*}$ （および、Activeな束縛条件に対する $\mathbf{a^*}$ ）は決定される。さらに、この（等式の束縛条件を持つ）停留値問題のdual functionについて、(1-2)が成り立つので、次が得られる（Inactiveな束縛条件に対しては、 $a^*_i=0$ とおく）。

$f(\mathbf{x^*}) = \tilde{L}(\mathbf{a^*})$

$a^*_i \ge 0$ については、次のように示せる。

$0 = \frac{\partial L(\mathbf{x},\mathbf{a})}{\partial \mathbf{x}}|_{\mathbf{x}=\mathbf{x^*},\mathbf{a}=\mathbf{a^*}} = \frac{\partial f(x)}{\partial \mathbf{x}}|_{\mathbf{x}=\mathbf{x^*}} - \sum_{i:Active}{a^*_i}\frac{\partial h_i(\mathbf{x})}{\partial \mathbf{x}}|_{\mathbf{x}=\mathbf{x^*}}$