制御工学で非線形計画のKarush-Kuhn-Tucker条件(KKT条件)を触れることがあったのでまとめる。非専門分野なのでご指摘頂けると嬉しいです。
この節では、不等式制約と等式制約付き非線形計画のKKT条件について触れる。KKT条件は、非線形計画問題の最適性の必要条件である。非線形計画は下式で与えるとする。
このときのKKT条件は下式で与えられる。このKKT条件を導出するのが本記事の目的である。
KKT条件をFarkasの補題を用いて導出する。局所最適解近傍に着目してFarkasの補題を用いて導出するのが基本的な方針である。
任意の行列
(1)
(2)
Farkasの補題から簡単な式変形をすることで系1を得る。
次の命題がいずれか一方が成り立つ。
(1)
(2)
Mangasarizan-Fronovitz制約を想定する(MF制約想定)。
MF制約想定とは
許容方向
不等式制約について、
十分小さい
等式制約について
十分小さい
しかし、
&&& KKT条件
&&&prf KKT条件の導出
式(3)より系1(2)が成り立たないことがわかる。よって、系1(1)が成り立つ。
等式制約と不等式制約を満足する必要があることを思い出せば下式を得る。
以上より、式(2.1)~(2.5)のKKT条件を得る。
引用
KKT条件をラグランジュ双対関数を用いて導出する。ラグランジュ双対関数とSlaterの制約に着目して、強双対定理を仮定してKKT条件を導出するのが基本的な方針である。
引用
この節では、不等式制約付き非線形計画のKKT条件について触れる。
非線形計画は下式で与えるとする。
このときのKKT条件は下式で与えられる。このKKT条件を導出するのが本記事の目的である。
KKT条件をFritz Johnの定理を用いて導出する。
局所最適解近傍に着目してGordanの二者択一の定理を用いてFritz Johnの定理を導出し、その後線形独立制約を想定してKKT条件を導出するのが基本的な方針である。はじめにFritz Johnの定理とGordanの二者択一定理を紹介し、Fritz Johnの定理を導出する。
不等式制約つき問題の局所最適解
任意の行列
(1)
(2)
式7より、
ただし、
Gordanの二者択一定理(1)が成り立たないので(2)が成り立つ。つまり、
まとめると、
不等式制約
線形独立制約を想定する。Fritz Johnの定理より
引用
Slaterの制約想定を仮定するとラグランジュ双対関数において強双対定理がなぜ成り立つのかまだ理解できていないです。
引用