やかんです。
この後最適化手法と数値解析の試験がありますが、最適化についてせっかくなのでメモります。
※以下、主問題と双対問題という概念は共に獲得済みであるとする。
KKTについて
KKTは、そのような状況下で「主問題しか見えていない」という気持ちになると理解しやすい。主問題しか見ないとき、その主問題について最適解x*が得られているのであれば、そのx*についてKKT条件を満たすようなλ、μが存在することを主張している。
ここで、「主問題しか見えていない」という気持ちをやめ、「双対問題も見えている」気持ちに切り替えると、主問題について最適解が得られるということはその主問題が実行可能であるということであり、KKT条件を満たすようなλ、μの存在は双対問題における最適解の存在を言っていると理解できる。
相補性について
相補性定理は、KKT条件の相補性条件（と符号条件）と同じ形をしていて、KKTにおいては「有効な制約以外の不等式制約は0に固定してもいいよね、というかむしろ0に固定してあげたときに辻褄が合わなくなるような場合は最適化じゃないよそれ」ということを主張している。
相補性定理においては、KKT条件が存在を主張しているのに対し、同じ事柄について「存在するときに以下の条件が満たされる」という主張をしている。
より具体的に述べると、相補性定理は「主問題も双対問題もどっちも解けたんだったら（最適解が得られたのであれば）、それぞれの最適解の間には以下のような関係が成り立っているはずだよ（言い換えると、そのような関係が成り立っていないのであれば、それは主問題か双対問題の少なくとも一方について説き間違えているよ）」といった主張をしている。
このとき、相補性定理が要求する条件というのは至ってシンプルで、主問題と双対問題の最適解がそれぞれ得られたという気になっているときに、
- 主問題が実行可能であること（主問題について得られた最適解が実行可能領域に属すること）
- 双対問題が実行可能であること（双対問題について得られた最適解が実行可能領域に属すること）
- 双対ギャップが0であること（強双対定理が支持されていること ← 支持されていないのであれば、それは主問題、双対問題のどちらかあるいは両方が改善可能ということであり、最適解ではない）
の3つが成り立っていますか？という条件である。
KKTと相補性について
両者は、同じことを言っている。
学習上の違いだと、KKTは双対性という概念を知らない状態でも学習可能なのに対し、相補性定理は双対性という概念を知っている必要がある。
実質的な違いをあえて言うのであれば、「存在する」という点を強調したい場合はKKT条件について述べると効果的で、「次のような関係性が成り立つ」という点を強調したい場合は相補性定理について述べると効果的、というくらいの理解でいる。
線形・非線形との関連
線形の場合は、ただKKT条件や相補性定理を考えるだけな気がするが、非線形の場合は「ラグランジアンを考える」という意識を強めてあげる方が理解が捗る気がしている。
ラグランジアンに関する双対問題は「ラグランジュ双対問題」として説明される。標準系の最適化問題の場合、ラグランジアンの値は常に目的関数以下になり、「ラグランジアンの最小値の最大化」を試みると目的関数の下界が得られる。その際、ラグランジアンについて実行可能領域について緩和することも有効である。
んー、、でもこれ、双対性って何を根拠に主張できるんだ？凸二次計画についてはもう標準形と双対問題が頭に入ってるから迷うことないんだけど、「ラグランジュ双対問題」という文脈で語られると、「なぜ双対問題たり得るのか」がいまいちわかってないなあ。
まあ、試験とか関係なくゆっくり理解を試みます。
ということで、以上です。試験頑張ってきます。数値解析はむずすぎ & 範囲広すぎでよくわかってません。
最後までお読みいただき、ありがとうございます！
