双対定理と数値的安定性

SDP の内点法では、一般的に Slater の条件を仮定していて、これによって双対定理が成り立っている。
しかし、duality gap が０になることは、もっと弱い条件でも証明できる。

この証明の方法を利用すると数値的に安定するのではないか？と思ったが、うまくいかないようである。
たとえば、graph partition problem は主問題側に実行可能解が存在しない典型的な例である。
これに証明の方法に沿って、最適解の集合を compact にする redundant な制約をいれてみたが、SDPA, SeDuMi で解いても数値精度はそれほど向上しない。

やはり、数値的安定性は難しい問題である。

今日の作業内容：数値的安定性チェック
今日のランチ：四川弁当　豚の角煮
明日の予測作業時間：4h