SDPA を使ってみよう
数理計画問題の1つである半正定値計画問題(SemiDefinite Programming)を解くsolverの1つであるSDPAのインストール方法についてまとめました.今回はbrew
コマンドは使えることを前提としています.brew
とはなんぞやという方はmac homebrew install
で検索してみてください. Macを使う際には必ず使うソフトウェアです.
今回使用した僕の環境です.
MacBook Pro 16
CPU: Intel Core i9
OS: macOS Catalina 10.15.6
1. ソースコードのダウンロード
以下のサイトから自分の環境に合ったソースコードをダウンロードします.
SDPA(Semidefinite Programming Algorithms) Official Page
このサイトではsdpa_7.3.8
が公開されている最新版のようです.
2. コンパイル
コンパイラの設定
実際に動作確認したコンパイラの環境は以下です. gcc-10
ではmumpsでコンパイルが通りませんでした.(僕の環境だけかもしれませんが...)
% brew install gcc@9
% which gcc-9 [~/sdpa/sdpa-7.3.8]
/usr/local/bin/gcc-9
% gcc-9 -v [~/sdpa/sdpa-7.3.8]
Using built-in specs.
COLLECT_GCC=gcc-9
COLLECT_LTO_WRAPPER=/usr/local/Cellar/gcc@9/9.3.0/libexec/gcc/x86_64-apple-darwin19/9.3.0/lto-wrapper
Target: x86_64-apple-darwin19
Configured with: ../configure --build=x86_64-apple-darwin19 --prefix=/usr/local/Cellar/gcc@9/9.3.0 --libdir=/usr/local/Cellar/gcc@9/9.3.0/lib/gcc/9 --disable-nls --enable-checking=release --enable-languages=c,c++,objc,obj-c++,fortran --program-suffix=-9 --with-gmp=/usr/local/opt/gmp --with-mpfr=/usr/local/opt/mpfr --with-mpc=/usr/local/opt/libmpc --with-isl=/usr/local/opt/isl --with-system-zlib --with-pkgversion='Homebrew GCC 9.3.0' --with-bugurl=https://github.com/Homebrew/homebrew-core/issues --disable-multilib --with-native-system-header-dir=/usr/include --with-sysroot=/Library/Developer/CommandLineTools/SDKs/MacOSX10.15.sdk SED=/usr/bin/sed
Thread model: posix
gcc version 9.3.0 (Homebrew GCC 9.3.0)
% export CC=gcc-9
% export CXX=g++-9
% export FC=gfortran-9
以上でコンパイラの設定は以上です.次は実際にコンパイルします.
OpenBLAS のダウンロード
% mkdir -p $HOME/sdpa
% cd $HOME/sdpa
% git clone https://github.com/xianyi/OpenBLAS.git
% cd OpenBLAS
SDPAのソースコードの解凍とmake
% cd $HOME/sdpa
% tar xzf sdpa_7.3.8.tar.gz
% cd sdpa-7.3.8
% export CFLAGS="-funroll-all-loops"
% export CXXFLAGS="-funroll-all-loops"
% export FFLAGS="-funroll-all-loops"
% ./configure --prefix=$HOME/sdpa --with-blas="${HOME}/sdpa/OpenBLAS/libopenblas.a" --with-lapack="${HOME}/sdpa/OpenBLAS/libopenblas.a"
% make
% make install
以上でcurrent directoryにsdpaバイナリができます.
3. テスト実行
% ./sdpa -h [~/sdpa/sdpa-7.3.8]
SDPA (Version 7.3.8) start at [Thu Sep 10 20:41:57 2020]
*** Please assign data file and output file.***
---- option type 1 ------------
./sdpa DataFile OutputFile [InitialPtFile] [-pt parameters] [-dimacs] [-numThreads numThreads]
parameters = 0 default, 1 fast (unstable), 2 slow (stable)
-dimacs : printout dimacs information incurring additional computation cost
-numThreads: Number of pthreads for internal computation
example1-1: ./sdpa example1.dat example1.result
example1-2: ./sdpa example1.dat-s example1.result
example1-3: ./sdpa example1.dat example1.result example1.ini
example1-4: ./sdpa example1.dat example1.result -pt 2
example1-5: ./sdpa example1.dat example1.result -dimacs
example1-6: ./sdpa example1.dat example1.result -numThreads 4
---- option type 2 ------------
./sdpa [option filename]+
-dd : data dense :: -ds : data sparse
-id : init dense :: -is : init sparse
-o : output :: -p : parameter
-pt : parameters , 0 default, 1 fast (unstable)
2 slow (stable)
-dimacs : printout dimacs information incurring additional computation cost
-numThreads: Number of pthreads for internal computation
example2-1: ./sdpa -o example1.result -dd example1.dat
example2-2: ./sdpa -ds example1.dat-s -o example1.result -p param.sdpa
example2-3: ./sdpa -ds example1.dat-s -o example1.result -pt 2
example2-4: ./sdpa -ds example1.dat-s -o example1.result -dimacs
example2-5: ./sdpa -ds example1.dat-s -o example1.result -numThreads 4
---- option type 3 ------------
./sdpa --version
to print out version and exit.
PARAMETER_FILE is decided by the following priority
1: The file assigned by '-p' option of 'option type 2'.
For 'option type1', this is skipped.
2: ./param.sdpa
For 'option type2', this is skipped.
3: /usr/share/sdpa/param.sdpa
4: Default parameter
より
% ./sdpa -ds example1.dat-s -o example1.result -p param.sdpa [~/sdpa/sdpa-7.3.8]
SDPA (Version 7.3.8) start at [Thu Sep 10 20:42:34 2020]
param is param.sdpa
data is example1.dat-s : sparse
out is example1.result
NumThreads is set as 1
Schur computation : DENSE
Entering DMUMPS driver with JOB, N, NZ = -2 0 0
mu thetaP thetaD objP objD alphaP alphaD beta
0 1.0e+04 1.0e+00 1.0e+00 -0.00e+00 +1.20e+03 1.0e+00 9.1e-01 2.00e-01
1 1.6e+03 0.0e+00 9.4e-02 +8.39e+02 +7.51e+01 2.3e+00 9.6e-01 2.00e-01
2 1.7e+02 2.3e-16 3.6e-03 +1.96e+02 -3.74e+01 1.3e+00 1.0e+00 2.00e-01
3 1.8e+01 2.9e-16 2.2e-17 -6.84e+00 -4.19e+01 9.9e-01 9.0e+01 1.00e-01
4 1.9e+00 2.6e-16 1.8e-15 -3.81e+01 -4.19e+01 1.0e+00 1.0e+00 1.00e-01
5 1.9e-01 2.7e-16 7.5e-18 -4.15e+01 -4.19e+01 1.0e+00 1.0e+00 1.00e-01
6 1.9e-02 2.8e-16 7.5e-18 -4.19e+01 -4.19e+01 1.0e+00 9.0e+01 1.00e-01
7 1.9e-03 2.9e-16 1.2e-15 -4.19e+01 -4.19e+01 1.0e+00 1.0e+00 1.00e-01
8 1.9e-04 2.8e-16 2.2e-17 -4.19e+01 -4.19e+01 1.0e+00 1.0e+00 1.00e-01
9 1.9e-05 2.7e-16 7.5e-18 -4.19e+01 -4.19e+01 1.0e+00 1.0e+00 1.00e-01
10 1.9e-06 2.9e-16 3.7e-18 -4.19e+01 -4.19e+01 1.0e+00 1.0e+00 1.00e-01
phase.value = pdOPT
Iteration = 10
mu = +1.9180668442023158e-06
relative gap = +9.1554505917001858e-08
gap = +3.8361336223147191e-06
digits = +7.0383202767393023e+00
objValPrimal = -4.1899996163866383e+01
objValDual = -4.1900000000000006e+01
p.feas.error = +3.5690251616723664e-14
d.feas.error = +3.5527136788005009e-15
total time = 0.001212
main loop time = 0.001063
total time = 0.001212
file check time = 0.000000
file change time = 0.000006
file read time = 0.000143
SDPA end at [Thu Sep 10 20:42:34 2020]
ALL TIME = 0.002608
と実行確認が取れます.
4. 参考文献
[1] http://sdpa.sourceforge.net/download.html#sdpa
[2] https://sourceforge.net/projects/sdpa/files/sdpa/sdpa-7.3.X-install.txt
[3] https://sourceforge.net/projects/sdpa/files/sdpa/sdpa.7.1.1.manual.20080618.pdf