確率最適化で非線形 SDP を解く

arXiv に SDP 関係の論文として
Faster Projection-free Convex Optimization over the Spectrahedron
http://arxiv.org/abs/1605.06203
が出てきていたので、大まかにチェック。

解きたい問題としては、 spectrahedron $\{ X : X \succeq O, tr(X) = 1\}$ 上で非線形の目的関数 $f(X)$ を最小化する最小化問題。
これについては、projected gradient method が既に提案されているが固有値計算が重たいので、それを回避する計算手法を検討している。

アイデアとしては、$x x^T$ の rank-1 行列を確率的に選んで、その方向での $f(X)$ の勾配を使って計算していく、という確率最適化計算手法になっている。
解析としては、どれくらいの反復が必要かという見積もりが中心。

数値計算結果としては、やはり反復をしても、あまり精度は得られていない様子。高精度な計算よりも、ある程度大雑把に計算結果を知りたいときになど用いるのが良さそう。ただし、projected gradient method との計算比較が載っていなかったりするので、それほど性能が良くない可能性もあり。

確率最適化の論文としては、なかなかに面白いと思う。