めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

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^*}}

したがって、

\nabla f(\mathbf{x^*}) = \sum_{i:Active}{a^*_i}\nabla h_{i}(\mathbf{x^*})

この時、下図より、a^*_i < 0 となるものが存在すると、束縛条件を満たす方向に \mathbf{x^*} を移動して f(\mathbf{x}) の値を小さくすることができるので、\mathbf{x^*} が最小値問題の解であることに矛盾する。

※ここで、Slater Condition \{\mathbf{x}|h_i(\mathbf{x}) > 0\} \ne \emptyset を仮定している。

まとめ

以上の議論に含まれていた各種条件を整理すると、次のようにまとめられる。

束縛条件 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とdual functionを次のように定義する。

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

\tilde{L}(\mathbf{a})\, := \min_{\mathbf{x}}L(\mathbf{x},\mathbf{a}) (定義域は、\mathbf{x}について下に凸で最小値を持つ範囲の\mathbf{a}

ここで、dual functionの最大値問題の解を \mathbf{a^*} とする。

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

この時、次の関係が成立する。

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

a_i^* \ge 0

h_i(\mathbf{x^*}) \ge 0

a_i^* \times h_i(\mathbf{x^*}) = 0

※最後の等式は、Activeな束縛条件については h_i(\mathbf{x^*}) = 0 で、Inactiveな束縛条件については、a_i^* = 0となることから成立する。