SCOPE（「計算と最適化の新展開」研究部会）第１回研究会

すでにメイリングリスト等にアナウンスも出ていますが、3月21日に第１回研究会を行います。s@co の最終回も2月28日にあります。

***************** SCOPE 第1回研究会 ************************

日時：2009年3月21日（土）14:00～
会場：中央大学 後楽園キャンパス 3号館3階 3309号室

講演者１：小島 政和 氏 （東京工業大学）
講演題目：半正定値行列補完における双対性とそのSDPへの応用

講演者２：村松 正和 氏 （電気通信大学）
講演題目：A Facial Reduction Approach in Conic Programming

***********************************************************

SCOPE（「計算と最適化の新展開」研究部会） ホームページ
SCOPE（「計算と最適化の新展開」研究部会）ブログ

SDP Relaxation と等式標準形

今回は業務連絡の様な内容なので、深い意味は無い。SDP を解こうとするときに、通常では SDP ソフトウェアの入力を作るために等式標準形に変換するという方法を用いる。ある SDP Relaxation を等式標準形に変換したのが添付の図になる。結構ややこしいのでどこかミスがあるかもしれない（ミスがあっても変換プログラムを作るときにわかる場合が多い）。今回はこの行列 Q が共分散行列なので、密行列になってしまう。残念ながら疎性の利用は最小限になる。

○定式化の資料に一部、訂正＆加筆を行った。

d-space & r-space conversion

SparseCoLO で用いられる以下の四つの conversion だが、SDP 自体が疎であることが重要なのではなく Schur complement 行列の疎性で conversion の効果が左右される。conversion が有効でないことは問題の SDP の特性からおおよそ判断できる。反対に有効であるかについては少しわかりにくい。

(a) The d-space conversion method using clique trees.
(b) The d-space conversion method using basis representation.
(c) The r-space conversion method using clique trees.
(d) The r-space conversion method using matrix decomposition.

添付の図は TSPLIB に含まれる pcb1173 という問題だが、これから Delaunay グラフを作り、そのグラフの max cut problem の SDP 緩和問題を作る。直観的には conversion が効きそうなので、試しに数値実験を行ってみた。SDPA での効果は少し微妙なところだが、SeDuMi で一番高速化される (b) のときに SDPA がもっとも遅くなっている。

○実行マシン：Intel Xeon 5460 (3.16GHz) : メモリ 48GB : CentOS 5.2 for x86_64 (4スレッドで実行)

1: conversion 無し
SDPA 7.2.1.rev7 : 19.173s(16反復)
SeDuMi 1.2 : 799.5s(14反復)

2: conversion (a)
SDPA 7.2.1.rev7 : 19.244s(17反復)
SeDuMi 1.2 : 610.1s(15反復)

3: conversion (b)
SDPA 7.2.1.rev7 : 58.475s(20反復)
SeDuMi 1.2 : 137.5s(17反復)

3: conversion (c)
SDPA 7.2.1.rev7 : 19.113s(16反復)
SeDuMi 1.2 : 868.2s(15反復)

3: conversion (d)
SDPA 7.2.1.rev7 : 19.128s(16反復)
SeDuMi 1.2 : 859.3s(15反復)

SDPA の改造 その３

前回に引き続いて SDPA 7.2.1.rev7 の数値実験を行う。実行マシン３の速度アップが非常に大きい。

○実行マシン１：Intel Xeon 5460 (3.16GHz) : メモリ 48GB : CentOS 5.2 for x86_64
○実行マシン２：Intel Core i7 965(3.2GHz) : メモリ 12GB : Fedora 10 for x86_64
○実行マシン３：AMD Opteron 2384 (2.7GHz) : メモリ 32GB : CentOS 5.2 for x86_64

問題１: D256.dat
○実行マシン１
SDPA 7.2.1 : 36.708s
SDPA 7.2.1.rev6 : 31.922s
SDPA 7.2.1.rev7 : 17.894s

○実行マシン２
SDPA 7.2.1 : 37.523s
SDPA 7.2.1.rev6 : 37.982s
SDPA 7.2.1.rev7 : 18.160s

○実行マシン３
SDPA 7.2.1 : 1m20.030s
SDPA 7.2.1.rev6 : 1m0.249s
SDPA 7.2.1.rev7 : 20.451s


問題２: gpp2000-10.dat-s
○実行マシン１
SDPA 7.2.1 : 2m12.263s
SDPA 7.2.1.rev6 : 2m12.979s
SDPA 7.2.1.rev7 : 2m2.478s

○実行マシン２
SDPA 7.2.1 : 1m32.245s
SDPA 7.2.1.rev6 : 1m31.426s
SDPA 7.2.1.rev7 : 1m27.524s

○実行マシン３
SDPA 7.2.1 : 2m9.733s
SDPA 7.2.1.rev6 : 2m9.846s
SDPA 7.2.1.rev7 : 2m1.401s

途中経過出力とブラウザ その２

前回触れた途中経過出力に関する問題は JavaScript 側の処理で解決するようにしている。ブラウザによって処理が異なることが開発を大変複雑にしている。添付の図が FireFox から実行したときの画面表示の例である。SDPA の出力結果ファイルは以下の A, B, C を含むのだが、画面表示はこのファイルから A と B だけを選んで表示するようになっている。

○SDPA の出力ファイルは以下の三つ部分で構成されている
A：各反復の情報（主問題、双対問題）　B：統計情報(主用部分、関数の実行時間、比率など）　C：最適解の解のデータ

興味のある方は http://laqua.indsys.chuo-u.ac.jp/portal/ から実行していただきたい。ある程度大きな問題でないと一度の多くの表示が行われてしまい、あまり面白くないかもしれない。

SparseCoLO: conversion してから SDPA で解く

SparseCoLO の使い方で SDPA Sparse format データ　→ conversion (Domain or Range) → SDPA Sparse format データの変換方法について。これで conversion 後のデータを用いて、SDPA, CSDP, SDPT3, SeDuMi 等で比較実験が出来る。fromSDPA 後に一度転置しなくてはならないようだ。

SparseCoLO
http://www.is.titech.ac.jp/~kojima/SparseCoLO/SparseCoLO.htm

>> fname='/home/fujisawa/src/sdplib/mcp124-1.dat-s';
>> [A,b,c,K]=fromsdpa(fname);
>> At=A';
>> J.f=size(At,1);
>> parCoLO.domain = 1; parCoLO.range = 0; parCoLO.EQorLMI = 1;
>> [x,y,infoCoLO,cliqueDomain,cliqueRange,LOP] = sparseCoLO(At,b,c,K,J,parCoLO);
Applying the d-space conversion method using clique trees
LOP to be converted into equality standard form is already equality standard form
SeDuMi 1.2 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
Detected 12 diagonal SDP block(s) with 12 linear variables
eqs m = 286, order n = 182, dim = 2256, blocks = 20
nnz(A) = 448 + 0, nnz(ADA) = 21396, nnz(L) = 10841
it : b*y gap delta rate t/tP* t/tD* feas cg cg prec
0 : 1.82E-02 0.000
1 : -7.82E+01 5.66E-03 0.000 0.3103 0.9000 0.9000 2.76 1 1 8.5E-01
2 : -1.21E+02 1.67E-03 0.000 0.2954 0.9000 0.9000 1.15 1 1 2.5E-01
3 : -1.36E+02 4.59E-04 0.000 0.2744 0.9000 0.9000 1.01 1 1 6.8E-02
4 : -1.40E+02 1.27E-04 0.000 0.2770 0.9000 0.9000 1.00 1 1 1.9E-02
5 : -1.42E+02 2.79E-05 0.000 0.2198 0.9000 0.9000 1.00 1 1 4.2E-03
6 : -1.42E+02 5.30E-06 0.000 0.1897 0.7645 0.9000 1.00 1 1 9.4E-04
7 : -1.42E+02 5.18E-07 0.000 0.0977 0.9900 0.9900 1.00 1 1 9.2E-05
8 : -1.42E+02 3.04E-08 0.067 0.0588 0.9900 0.9900 1.00 1 1 5.4E-06
9 : -1.42E+02 5.71E-09 0.000 0.1875 0.9000 0.9000 1.00 1 1 1.0E-06
10 : -1.42E+02 1.02E-09 0.000 0.1782 0.9000 0.9000 1.00 1 1 1.8E-07
11 : -1.42E+02 1.87E-10 0.000 0.1840 0.8910 0.9000 1.00 2 2 3.3E-08
12 : -1.42E+02 3.55E-11 0.000 0.1899 0.8841 0.9000 1.00 28 41 6.3E-09
13 : -1.42E+02 3.36E-12 0.481 0.0946 0.9900 0.9847 1.00 66 75 6.0E-10

iter seconds digits c*x b*y
13 0.3 Inf -1.4199047705e+02 -1.4199047705e+02
|Ax-b| = 2.1e-09, [Ay-c]_+ = 4.5E-10, |x|= 3.4e+01, |y|= 1.7e+01

Detailed timing (sec)
Pre IPM Post
1.000E-02 3.000E-01 0.000E+00
Max-norms: ||b||=1, ||c|| = 1.750000e+00,
Cholesky |add|=0, |skip| = 23, ||L.L|| = 398.093.

>> writeSDPA('mcp124-1D.dat-s',LOP.A,LOP.b,LOP.c,LOP.K);
## Write SeDuMi SDP data to the file tmp.dat-s.

SDPA の改造 その２

SDPA 7.2.1.rev7 が出来たので、簡単に数値実験結果を載せておく。変更点は以下の通り。
１： BLAS の daxpy 関数のインクリメントを 1 に変更するために、Schur complement 行列の F1 式関係を少し変更
２： Schur complement 行列の計算量見積り式にデータ移動量も加えて全般的に見直しを行った

SDPA 7.2.1.*** + GotoBLAS 1.29 + MUMPS 4.8.3 (OMP_NUM_THREADS=4 ; 4 スレッドで実行)
○実行マシン：AMD Opteron 2384 (2.7GHz) : メモリ 32GB : CentOS 5.2 for x86_64
Intel Core i7 965(3.2GHz) : メモリ 12GB : Fedora 10 for x86_64

問題１: D256.dat
SDPA 7.2.1 : 1m20.574s
SDPA 7.2.1.rev6 : 59.527s
SDPA 7.2.1.rev7 : 20.949s

問題２: gpp2000-10.dat-s
SDPA 7.2.1 : 2m9.627s
SDPA 7.2.1.rev6 : 2m6.623s
SDPA 7.2.1.rev7 : 2m3.588s

途中経過出力とブラウザ

前回ちょこっと説明した新 SDPA Online Solver の途中経過出力機能だが、ブラウザによっては(IE や Firefox)正常、あるいは意図したように表示がされていない。IE は論外としても Firefox で動作しないのはまずいので、いろいろと修正することにした。Firefox と Javascript (Prototype.js)の相性なのか仕様なのかわからないが、テキストファイルの改行が空白として表示されるので、対策として SDPA の出力ファイルを HTML 形式で作る方法がある(改行部分は と置き換える)。
現在の SDPA 7.2.1 は本体が callable library 化(libsdpa.a)されているので、sdpa_exe.cpp というソースファイルから library の API を呼び出している。つまり sdpa_exe.cpp は callable library 使用のサンプルソースファイルでもある。この特性を生かして次のようなプログラムを作成する。

○SDPA の出力ファイルは以下の三つ部分で構成されている
A：各反復の情報（主問題、双対問題）　B：統計情報(主用部分、関数の実行時間、比率など）　C：最適解の解のデータ
A は実行時の各反復ごとに出力される。B と C は終了時に出力される。一般には元問題のサイズが大きいと C の出力データのサイズも大きくなる。C のデータはファイルとしては必要だが、ブラウザで見るときには不必要（むしろ邪魔？）
○SDPAから二種類の出力ファイル生成する
１：上記の A と B を含み HTML 形式で出力する
２：上記の A, B, C を含みテキスト形式で出力する（いままでと同じ）
１だけとブラウザで閲覧する対象とする
○これらの変更は SDPA 本体も一部変更する必要があるが、両者の切り替えについては sdpa_exe.cpp の部分で吸収が可能である

新 SDPA Online Solver の仕様 その２

前回の記事は外見に関する説明だったので、今回は中身に関して説明を行いたい。とは言っても細かい説明は分量が必要になるので、概要と現システムとの違いについて述べる。
１：現システム Ninf-1 (Ninf-G & Globus) → 新システム Ruby & ssh (port forward も含む)
２：ソルバーの出力ファイルを定期的に Web サーバにコピーして、その内容を表示する → ユーザが途中経過を知ることが出来るようになった
３：外部サーバとの通信に用いるポートは ssh(22番)のみ
４：Online Solver というよりも SDPA 本体に自動データ構造＆計算方法決定機能が付いているので、ユーザはデフォルトパラメータで実行すれば良い

新 SDPA Online Solver の仕様 その１

新 SDPA Online Solver は開発中であるが、すでに公開も行っている。
http://laqua.indsys.chuo-u.ac.jp/portal/

もともと何の保証もないシステムであるが、新システムの方はほぼ毎日変更しているので、実行中に仕様が変わってしまうこともあるかもしれない。登録されているソフトウェアもあまりデバッグ作業にも時間をかけていない出来立ての最新版を使っていることも多いので、安定性を重視される方は
http://sdpa.indsys.chuo-u.ac.jp/portal/
の方を使用していただきたい。

○登録ソルバーと計算サーバ
1: SDPA 7.2.1.rev7 + GotoBLAS 1.29
計算サーバ：AMD Opteron 2384 2.7GHz(４コア) x 2 個 : メモリ 32GB : CentOS 5.2 for x86_64

2: SDPARA 7.2.1 + GotoBLAS 1.29 + MUMPS 4.8.3
計算サーバ : Intel Xeon 5460 3.16GHz(４コア) x 2 個 x 16 ノード : メモリ 48GB : OS : CentOS 5.2 for x86_64
Linpack : R_max = 1.435TFlops, R_peak = 1.618TFlops, R_max / R_peak = 88.69%

3: SDPA-GMP 7.1.2
計算サーバ : Intel Xeon 5160 3GHz(４コア) x 2 個 : メモリ 8GB : OS CentOS 5.2 for x86_64

4: SDPA 7.2.1.rev7
計算サーバ(Amazon EC2) : AMD Opteron 2218(仮想マシン１コア) 2.6GHz x 1 個 : メモリ 1.7GB : OS Fedora 8 Xen (仮想マシン)

1.4TFlops のクラスタや Amazon EC2 などもあり、全体としてまとまりはないが楽しい構成になっている。

SCOPE（「計算と最適化の新展開」研究部会）

この３月から日本オペレーションズ・リサーチ学会 研究部会”計算と最適化の新展開　Seminar on Computation and OPtimization for new Extensions (SCOPE)”の主査を努めることになりました。とりあえずブログを開きました。ホームページも作成中ですが、ブログの方が主流になるかもしれません。詳しくは以下をご覧下さい。
http://blog.goo.ne.jp/scope_or/

新 SDPA Online Solver のシステム その２

新 SDPA Online Solver の公開までもう少しとなっている。正確にはすでに公開はしているのだが、現在はフル規格で動作してしていない。現システムと異なるのは実行終了時までにいつでも何回でもクライアントとサーバが通信する（通信できる）ところにある。こういった用途を考慮すると簡単、高機能、安全なのは Globus などではなくて、やはり ssh の利用ということになる。
新システムの大きな特徴の一つとしては、ユーザーが現在の状態（途中結果）を入手できることにある。それに新システムでは SDPA-GMP も組み入れる計画になっているが、この場合では途中で実行を打ち切る場合も出てくる。時間制限は Torque 側で設定しても良いのだが、ユーザーに途中結果を渡すことが必要になる。また試験的に計算資源に Amazon EC2 の仮想マシンを付け加える予定である。

SDP の前処理 (SparseCoLO)

以下の SDP 用の疎性を利用した前処理ツール SparseCoLO が公開されることになった。

http://www.is.titech.ac.jp/~kojima/SparseCoLO/SparseCoLO.htm

全部の SDP に対して有効ではないが、この conversion が有効な問題の特性はだいだい掴むことができる。

1: 現在は MATLAB のプログラムだが、C/C++ に変更した方が高速化、汎用性の向上が期待できる。MATLAB を C/C++ のソースに直すのではなく、一から作り直した方が長期的には得になる
2: SDPA Online Solver の中にこの前処理のプログラムを入れてしまうのも良さそう。

SparseCoLO is a Matlab package for implementing the four conversion methods, proposed by
Kim, Kojima, Mevissen, and Yamashita, via positive semidefinite matrix completion for an optimization
problem with matrix inequalities satisfying a sparse chordal graph structure. It is based
on quite a general description of optimization problem including both primal and dual form of
linear, semidefinite, second-order cone programs with equality/inequality constraints. Among the
four conversion methods, two methods utilize the domain-space sparsity of a semidefinite matrix
variable and the other two methods the range-space sparsity of a linear matrix inequality (LMI)
constraint of the given problem. SparseCoLO can be used as a preprocessor to reduce the size of
the given problem before applying semidefinite programming solvers.

SDPA-GMP 7.1.2 リリース その２

SDPA 7.2.1 などを実行すると以下のマシン２の方がマシン１よりも１、２割速いことが多く、メモリバンド幅もマシン２はマシン１の３～４倍速いのだが、SDPA-GMP 7.1.2 では以下のようにマシン１とマシン２での結果がほとんど変わらない。

○ソフトウェア： SDPA-GMP 7.1.2 + GMP 4.2.4
○実行マシン１：Intel Xeon 5460 (3.16GHz) : メモリ 48GB : CentOS 5.2 for x86_64
○実行マシン２：Intel Core i7 965(3.2GHz) : メモリ 12GB : Fedora 10 for x86_64
○実行マシン３：AMD Opteron 2384 (2.7GHz) : メモリ 32GB : CentOS 5.2 for x86_64

1: mcp124-1.dat-s
○マシン１ : 47.451s
○マシン２ : 46.547s
○マシン３ : 55.280s

2: theta2.dat-s
○マシン１ : 3m32.789s
○マシン２ : 3m28.092s
○マシン３ : 4m2.518s

3: meter-2.dat-s
○マシン１ : 35.161s
○マシン２ : 33.311s
○マシン３ : 40.694s

SDPA-GMP 7.1.2 と 7.1.1

SDPA-GMP 7.1.2 と 7.1.1 では問題によって差が大きくなったり、減ったりする現象が見られる（以下のように）。反対に 7.1.2 で遅くなる場合もある。

○ソフトウェア： SDPA-GMP 7.1.1 と SDPA-GMP 7.1.2 + GMP 4.2.4
○実行マシン１：Intel Core i7 965(3.2GHz) : メモリ 12GB : Fedora 10 for x86_64
○実行マシン２：AMD Opteron 2384 (2.7GHz) : メモリ 32GB : CentOS 5.2 for x86_64

問題１ : mcp124-1.dat-s
実行マシン１
SDPA-GMP 7.1.1 : 68.580s
SDPA-GMP 7.1.2 : 46.370s
実行マシン２
SDPA-GMP 7.1.1 : 70.370s
SDPA-GMP 7.1.2 : 53.270s

問題２ : theta2.dat-s
実行マシン１
SDPA-GMP 7.1.1 : 216.750s
SDPA-GMP 7.1.2 : 206.450s
実行マシン２
SDPA-GMP 7.1.1 : 221.770s
SDPA-GMP 7.1.2 : 230.100s

問題３ : mater-2.dat-s
実行マシン１
SDPA-GMP 7.1.1 : 39.170s
SDPA-GMP 7.1.2 : 33.100s
実行マシン２
SDPA-GMP 7.1.1 : 40.600s
SDPA-GMP 7.1.2 : 39.830s

そこで問題１(実行マシン１)について gprof でプロファイルを行ってみた。__gmpn_addmul_1 や __gmpf_sub は変わらないが、__gmpf_mul と __gmpf_add は 7.1.2 の方が速くなっている。
○SDPA-GMP 7.1.1
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
15.44 9.05 9.05 __gmpn_addmul_1
13.62 17.04 7.99 __gmpf_mul
9.76 22.76 5.73 __gmpf_add
6.07 26.32 3.56 _int_malloc
5.10 29.31 2.99 __gmpf_sub

○ SDPA-GMP 7.1.2
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls s/call s/call name
21.44 9.04 9.04 __gmpn_addmul_1
12.13 14.16 5.12 __gmpf_mul
8.93 17.92 3.77 __gmpf_add
7.07 20.90 2.98 __gmpf_sub
6.36 23.58 2.68 __gmpn_mul_basecase