トップページ

ソフトウェア



半正定値計画問題を主双対内点法で解くソフトウェア SDPA (SemiDefinite Programming Algorithm) を、共同開発しています。使用言語は C++です。ソースコードはインターネット上で公開していますので、ダウンロードしてコンパイルすれば、誰でも半正定値計画問題を解くことができます。

SDPAのホームページ

また、インターネットを利用して online で解くこともできます。

SDPA Online Solver

NEOS Solver : SDPA はこちら


SDPAとその派生版

名前
説明
SDPA
基本バージョン
SDPA-M
SDPA を Matlab 上から動かす
SDRARA
SDPA の並列計算 (MPIを使用)
SDPA-C
SDPA に行列補完理論を導入
SDPARA-C
SDPA-C の並列計算
SDPA-CG
SDPA の線形方程式系に共役勾配法を適用 (非公開)
SDPA-R
SDPA の安定性を高める (非公開)
SDPA-S
多くのブロック対角を持つ SDP を効率良く解く (非公開)


とりあえず解いてみる

NEOS server 上の SDPA を使って半正定値計画問題を解く手順について説明します。 例として、以下のSDP問題を解いてみましょう。

SDP問題

  1. 問題を SDPA sparse format で記述します。
    • 以下のような感じになります。実際の入力データファイルはこちら
    • 詳しい説明はSDPAのマニュアルを参照して下さい

      2             ← 線形制約の数
    1 ← とりあえず1にする
    3 ← 行列の次元
    7 -2 ← 線形制約の右辺の値を順番に並べる
    0 1 1 1 5 ↓ 以下では行列に関して記述する
    0 1 1 2 1    一行が行列の非ゼロ要素一つに対応し、k番目の行列の
    0 1 1 3 2    (i,j)要素の値が v のとき、k 1 i j v と並べる。
    0 1 3 3 3    ただし、
    1 1 1 1 1    ・目的関数に現れる行列は、0番目と考える
    1 1 2 2 1    ・対称行列なので、上半分(対角を含む)のみ記述する
    1 1 3 3 1  
    2 1 2 3 6

  2. NEOS server に問題を送る
    1. http://neos.mcs.anl.gov/neos/solvers/sdp:SDPA/SPARSE_SDPA.html に飛ぶ
    2. SDPA data(local file):    の欄に入力データファイル名を入れる
    3. Submit to NEOS      をクリック

  3. しばらく待つと結果が表示される(上の問題ならば数秒で解けます)
    もし 2.で e-mail address:  の欄に自分のメールアドレスを入力しておけば、結果がメールでも送られてきます

  4. 出力結果を調べる
    このような画面が現れますが、大事な部分は以下の項目です。 (詳細はSDPAのマニュアルを参照して下さい)
    • phase.value =     pdOPT ならば解けています
    • gap =                誤差の上界です
    • objValDual =       最適値です
    • yMat =              最適解です

    つまり、この問題の最適値は 4.3039951985e+01 で、最適解は
    { {+4.916e+00, -2.568e-01, +3.191e+00 },
    {-2.568e-01, +1.341e-02, -1.667e-01 },
    {+3.191e+00, -1.667e-01, +2.071e+00 } }
    という行列になります。


トップページに戻る