KKT条件について
非線形計画問題に対するKKT(Karush-Kuhn-Tucker)条件についてまとめてみましたのでPDFを公開いたします.
このPDFでは, 例えば, 制約条件として不等式制約のみ持つ問題に対しては, Slater制約想定やCottle制約想定のもとで(局所最適解において)KKT条件が成り立つことを示し, 等式制約も含む問題に対しては, 一次独立制約想定やMangasarian-Fromovitz制約想定のもとでKKT条件が成り立つことを示しています.
特にMangasarian-Fromovitz制約想定のもとでKKT条件が成り立つことについては, 証明が載っている和書が限られている上に, 書いてあっても行間があって読みにくいので, きっと誰かの役に立つはず...
証明には, Farkasの補題やGordanの定理といった, 分離定理に深い関わりのある事実を用いています. もちろん, この事実の証明も与えています.
なお, より一般の制約想定(Abadie, Guignard制約想定など)のもとでKKT条件が成り立つことの証明も述べており, それら制約想定間の関係についても詳述しております.
読むために必要な知識は, の位相, 微積, 線型代数の基礎です. より詳しく言えば, 開集合, 閉集合, 一次独立という言葉や微分の定義, および有界閉集合上で連続関数が最大値最小値を持つことなど基本的なことを知っていれば読めるはずです.
数学的な誤りや打ち間違いなどがありましたらコメント頂けると幸いです.
2020/08/26 追記: ありがたいことに早速ひとりの方に読んでいただき数多くの誤植を指摘していただきました. リンク先は修正版になっております. よろしくお願いします.
2020/08/27 追記: 上記の方と同一人物ですが, 現在, RKさん(ツイッターID:@evindem)にPDFを精読していただいており, 第4章までの誤りを指摘していただきました. リンク先は修正版になっております. 今後も誤りが見つかるごとに, 修正版をアップロードしていきますのでよろしくお願いします.
2020/09/02 追記: 先日RKさんに最後まで読んでいただきました. その際に指摘していただいたミスの修正をしました. また, 局所最適解の必要条件の解釈について加筆いたしました. よろしくお願いします.