研究集会に参加してきた

今日は政策研究大学院大学での研究集会に参加してみて、あまり長い時間はいられなかったけど、どれも面白い話だった。

まずは、ＳＤＰで主問題と双対問題の両方に内点がないような問題で、その場合には「ほぼ確実に」双対ギャップがある、という話だった。
面白いのは、元の主問題を摂動した SDP の目的関数値は双対問題の値に近くなる、ということだと思う。つまり、摂動SDPの最適値と双対問題の間にあるギャップが分かれば、双対問題の値を求められるわけで、内点法では解けないような問題が解けるようになるかもしれない。

あと、クラスタリングの方法は、ある基準を満たせば凸計画問題で最適なクラスタリングができる、という理論的側面の話があった。
この基準について、どれくらいタイトなのか、というところが分かると、さらに面白いなぁ、と思う。つまり、その基準に使っている値よりも少しでも大きいと最適でないクラスタリングが作れるかどうか、ということ。

もう一つは機械学習系の DC アルゴリズムの話で、こちらの数値実験は精度が 10^{-5} ぐらいの緩いところでは matlab の fmincon よりも速い、という話だった。ただ、matlab の fmincon は汎用ソルバーなので、Lipshitz 条件を満たさない関数でも扱えるはずだから、fmincon よりも速い、というのは妥当なところかと思う。
個人的には、||x||_0 <= k の制約を ||x||_0 = k にも置き換えられたら、もっといろんな問題も解けるなぁ、と思ったり、あとは停留点だけでなくて Robinson 条件とかも満たしているかどうか調べると面白そう、と思ったりした。


やっぱり、たまに他のところで話を聞いてくると、いろいろと思いついたりでいいなぁ。