非負かつ半正定値(DNN : doubly non‐negative)制約を両方使用すると SDP 緩和の最適目的関数値が元の問題の最適目的関数値に非常に近い値になる件の続きになる。
1: 現在以下の二つの問題を試しているが、元問題は非凸QP(二次計画問題)になる。これから DNN 制約付き SDP 緩和問題を作る。非負制約によって元問題の凸包に近くなるのではないか?(特に根拠はなし)
2: 非負制約によって制約条件の数が増大する。これから Schur complement 行列の Cholesky 分解がボトルネックになる。
以下は SDPARA 7.2.1.rev8 + GotoBLAS 1.34 + MUMPS 4.8.4 を SDPA クラスタ上で実行したときの結果になる。A と B 両方とも非凸QP に DNN 制約付き SDP 緩和問題を作っている。
A: QAP(二次割当問題)
had20 : 総計算時間 10464.2s
Cholesky bMat = 8472.634236s, 80.973215%
B: Portfolio Selection(ポートフォリオ選択問題)
200101 : 総計算時間 1240.5s
Cholesky bMat = 823.754049s, 66.415721%
1: 現在以下の二つの問題を試しているが、元問題は非凸QP(二次計画問題)になる。これから DNN 制約付き SDP 緩和問題を作る。非負制約によって元問題の凸包に近くなるのではないか?(特に根拠はなし)
2: 非負制約によって制約条件の数が増大する。これから Schur complement 行列の Cholesky 分解がボトルネックになる。
以下は SDPARA 7.2.1.rev8 + GotoBLAS 1.34 + MUMPS 4.8.4 を SDPA クラスタ上で実行したときの結果になる。A と B 両方とも非凸QP に DNN 制約付き SDP 緩和問題を作っている。
A: QAP(二次割当問題)
had20 : 総計算時間 10464.2s
Cholesky bMat = 8472.634236s, 80.973215%
B: Portfolio Selection(ポートフォリオ選択問題)
200101 : 総計算時間 1240.5s
Cholesky bMat = 823.754049s, 66.415721%