SNL の講演を聞く

今日は、SNL の講演を聞いた。
SDP 緩和に持ち込むのではなく、clique それぞれの内部でお互いの座標を固定しておいて、それから clique どうしをつなぐ、というアイデアだった。
SFSDP とは clique の作り方がまったく異なるので、すぐに2つをつなげることはできないが、うまく組み合わせれば、これまで以上に大きな SNL が解けるかもしれない。
あと、SNL については、
James Aspnes, David Goldenberg, and Yang Richard Yang.
"On the computational complexity of sensor network localization."
という論文があり、これを読むと NP=P でない限り、SNL には効率的に厳密解を見つける方法はない、ということが証明されているらしい。

あとは、SDPARA の原稿の続き。
数値実験にどの問題を解くかを考えている最中であるが、sparsePOP の examples の問題を試しに調べたら、correlative sparsity が多くの問題で似通った形になることが分かった。
なので、この中からはひとつをピックアップすればいいかと考えている。

ところで、correlative sparsity を計算するのを matlab に任せているが、いくかの問題の correlative sparsity pattern を調べるのに matlab でひとつひとつコマンドを入力するのも大変になってきたので、明日あたり、自動化しようと思う。

今日の作業: SNL 4h + 原稿 2h
今日のBGM: FF5 OST [1-2]
今日のランチ: らく うな重
明日の予測作業時間: 6h