SDPA の今後について

つくばSAOR1とつくばSAOR2のお話に関して今日は SDP(半正定値計画問題)についてまとめてみます。つくばでの研究会では SDP 関連の講演が多かったそうです（半分は内輪かも）。また K 師匠によるとスウェーデンの SIOPT でも、かなり SDPA について関心も持ってもらったそうです。
K 師匠だったと思いますが、SDP は 21世紀の線形計画問題(LP)と言ってました。私もかつての LP のように気軽に SDP を使ってと言ってます。単なる SDP でしょ、そんなのは軽いと言うわけです（少し大胆ですが）。

SDPA の開発チームも大変増えて（ざっと７人はいます：K, F, N, Y, F, K, F)、おそらく世界中全ての SDP 開発チームのなかで最大だと思います。本当にいろいろなバージョンがありますというか、出来てきました。こちらも参照してください。

1: SDPA (SDP を解くための主双対内点法のソフトウェア。もっとも基本的でノーマルなソフト。最も古く、格が最上。1995年より公開中）
2: SDPA-CG (Shur Complement 行列の線形方程式を解くために CG 法を用いている。良い条件の前処理方法が見つからなかったので、特殊な場合のみ有効。公開していない）
3: SDPA-C (入力問題の疎性の処理に行列補完による方法を用いている。公開中だが使用は SDPA-C の並列版 SDPARA-C をお勧めします)
4: SDPARA (SDPA のボトルネックの部分を MPI を用いて並列化したもの、SDPA と並ぶ主力ソフトウェア。公開中)
5: SDPARA-C (SDPA-C を並列化したもの。並列化思想は SDPARA とほぼ同じ。公開中。問題によっては全 SDPA の中で最速を誇る）
6: SDPA-M (SDPA に Matlab インターフェイスを付けたもの。当初の予定を裏切って意外とユーザーが多い。公開中。このために米国 V 大の F 君にもチームに参加してもらってます）
7: SDPA-S (基本はSDPA。Shur Complement 行列が疎になる場合に対応しているが、その変更が様々な場所に波及して、全体的に疎データのために書き直しになっている。現在非公開）
8: SDPA-R (SDPA の Robust 版。速度よりも精度や安定性を重視している。現在非公開）
9: SDPA-? (SDPA で等式制約をそのまま扱えるようにしている。現在非公開。名前も正式に決まっていない）

以下に今後の課題や計画について書いて見ます。

1: 上記のように様々なバージョンがあるので、ユーザーは混乱してしまうかもしれない。そのために二つの方法を考えている。一つ目は、前処理用のプログラムを作成する。入力問題を読んで、問題のサイズや疎性などから適切なソフトウェアを選択したり、適切なデータ構造に変換したりする。二つ目は Online Solver を提供して、ユーザーにいろいろ試してもらって適切なソフトウェアを選択してもらう。現在開発中の WebSDPA はこのためにも重要。この件ではお世話になっております。
2: SDP の解くための方法には、主双対内点法、双対内点法、ラグランジュ関数を用いた非線形最適化のアルゴリズムなどがあるが、それらの優劣、長所短所についての自己調査（他人の調査ではなく）。
3: SDPARA のグリッド化。SDPARA は並列化による効果によって、その性能を誇っているが、いずれ他のグループも追随してくるので、一歩先に GridMPI などを用いてグリッド化してしまおうと思う。

上記の 1, 2, 3 に関しては新しい人材も欲しいですね。