論文読み：On Polyhedral and Second-Order-Cone Decompositions of Semidefinite Optimization Problems

Optimization Online に出てきていた
"On Polyhedral and Second-Order-Cone Decompositions of Semidefinite Optimization Problems"
http://www.optimization-online.org/DB_HTML/2019/09/7392.html
をザックリと読んでみた。

基本的には、半正定値条件をＬＰだったりＳＯＣＰだったりで近似する、という話だった。
近似して解いた後に、半正定値条件を満たしていなければ、切除平面を入れて解きなおしている。

数値実験は Sparse PCA と nuclear norm 最小化を扱っていて、やはり、問題が大きなものには近似でやったほうが大きなサイズが解けるようだ。
SOCPで半正定値条件を近似すると、切除平面法の収束は普通には結構な反復回数が必要なので、Sparse PCA や nuclear norm 最小化は問題の構造が比較的簡単なのかもしれない。