Uzawa method の実装に挑戦

ICCOPTで勉強してきた Uzawa method をSDPについて実装を行ってみた。
コアとなるアルゴリズムは、Matlab なら 30 行程度で実装できる。

１反復当たりの計算量はADMM よりも小さい（計算量オーダーで違う）ので、各反復は高速だが、やはり収束までの反復回数が相当かかる。

特に、理論的に収束させるためのステップ幅が 1.0e-5 よりも短くなるのが厳しい。
適当にステップ幅を大きくすると、当然ながら点列は収束しないで、どっか明後日の方向に飛んでってしまう。

SDPA にある example1.dat-s なら 100 反復程度なので結構高速だが、SDPLIB にある control1.dat-s を解こうとしたところ 100 万反復（「万」に注意）しても、解に近づけなかった。

ちなみに、「Uzawa method は双対問題への劣勾配法に相当する」、と書いてある論文があった。

やはり参考にしている元論文と同じように特定の状況のみに使うべきか、あるいは、もう少し別のスピードアップを検討するべきか。Uzawa method は、もともと広範囲のアルゴリズムなので、スピードアップについてもいろいろと研究があることだし。