Renegar の first-order method

Nesterov の first-order method を、Renegar が SDP 用にしたものが arXiv で読むことができる。

Efficient First-Order Methods for Linear Programming and Semidefinite Programming
James Renegar
http://arxiv.org/pdf/1409.5832v2.pdf

SDP の定式化を変形することによって、Nesterov の手法を使えるようにする、というのがミソで、この変形を行うと制約式が線形制約だけになる。（問題のむずかしさが目的関数に集約される感じか。）


なかなか面白い手法ではあるが、その一方で
Practical first order methods for large scale semidefinite programming
Stephen Tu, Jingyan Wang
http://www.cs.berkeley.edu/~stephentu/writeups/first-order-sdp.pdf
を見るとソフトウェアへの実装は難しいようである。
どのあたりに難しさがあるのか、ということを確認すると、新しい研究に結びつくかもしれない。