SDP relaxation の論文チェック

今日は、以下の５本の SDP relaxation の論文をチェックした。

[1] Ge and Ye, "On Doubly Positive Semidefinite Programming Relaxations", 2010, Optimization Online
[2] He, Luo, Nie and Zhang, "Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization", 2007, たしか Optimization Online
[3] Luo, Ma, So, Ye and Zhang, "Semidefinie Relaxation of Quadratic Optimization Problems", 2010, IEEE Signal Processing Magazine 20
[4] Nesterov, "Semidefinite relaxation and nonconvex quadratic optimization", 1998, Optimization Methods and Software 9
[5] Ye, "Approximating quadratic programming with bound and quadratic constraitns", 1999, Math Prog 84


[1] については最近のもので、quadratic constraind quadratic proggramming (QCQP) について、SDP 緩和と Doubly-Non-Negative (DNN) 緩和の場合で、どれだけの差があるか、というもの。DNN 緩和だからといって SDP 緩和よりも良くならないことがある、DNN緩和で SDP 緩和よりも改善できる場合でも改善量には限界がある、などが指摘されている。

[2] については、quadratic な制約のみで homogeneous。いろいろな場合を示しているが、それぞれの場合が特殊過ぎる印象。

[3] は信号処理の研究者向けに SDP relaxation をまとめたもの。基本的なところは、Goemans and Williamson をやはりベースにしている。SDP relaxation でどの位の比率で計算できるか、がまとまっている点は、あとで参考にしやすい。

[4] は、nonconvex quadratic optimization でどの程度のことができるかを Goemans and Williamson を拡張する形で展開。

[5] は、[4] をさらに拡張しているが、証明のテクニックは [4] とほぼ同じ流れ。


まとめると、Goemans and Williamson の論文が基本中の基本であって、これを拡張するときに[4]の証明方法が参考になる。

明日は、Goemans and Williamson の論文ともう1本論文をチェックして、どれがつかえそうかピックアップする。

今日の作業内容：SDP relaxation 5h + 解析力学 1h
今日のBGM: Xenosaga III OST [1-2], FF5 OST [1-2]
今日のランチ： シッダルータ ほうれんそうとマッシュルームのカレー
明日の予測作業時間：6h