Research Reports on
Mathematical and
Computing Sciences
Department of
Mathematical and
Computing Sciences
Tokyo Institute of Technology
SERIES B:
O
OO
p
pp
e
ee
r
rr
a
aa
t
tt
i
ii
o
oo
n
nn
s
ss
R
RR
e
ee
s
ss
e
ee
a
aa
r
rr
c
cc
h
hh
ISSN 1342-2804
SDPA (SemiDefinite Programming Algorithm)
and SDPA-GMP User’s Manual — Version 7.1.2
Katsuki Fujisawa, Mituhiro Fukuda, Kazuhiro
Kobayashi, Masakazu Kojima, Kazuhide Nakata,
Maho Nakata, and Makoto Yamashita
June 18th 2008, B–448
Research Report B-448
Department of Mathematical and Computing Sciences
Tokyo Institute of Technology
June 2008
SDPA (SemiDefinite Programming Algorithm) and SDPA-GMP
User’s Manual — Version 7.1.2
Katsuki Fujisawa
∗1
, Mituhiro Fukuda
∗2
, Kazuhiro Kobayashi
∗3
, Masakazu Kojima
∗4
,
Kazuhide Nakata
∗5
, Maho Nakata
∗6
, and Makoto Yamashita
∗7
Abstract. The SDPA (SemiDefinite Programming Algorithm) [5] is a software package for solv-
ing semidefinite programs (SDPs). It is based on a Mehrotra-type predictor-corrector infeasible
primal-dual interior-point method. The SDPA handles the standard form SDP and its dual. It
is implemented in C++ language utilizing the LAPACK [1] for matrix computations. The SDPA
version 7.1.2 enjoys the following features:
• Efficient method for computing the search directions when the SDP to be solved is large
scale and sparse [4].
• Block diagonal matrix structure and sparse matrix structure are supported for data matrices.
• Sparse or dense Cholesky factorization for the Schur matrix is automatically selected.
• An initial point can be specified.
• Some information on infeasibility of the SDP is provided.
Also we provide the SDPA-GMP, multiple precision arithmetic version of the SDPA via the
GMP Library (the GNU Multiple Precision Arithmetic Library) with additional feature.
• Ultra highly accurate SDP solution by utilizing multiple precision arithmetic.
This manual and the SDPA can be downloaded from the WWW site
http://sdpa.indsys.chuo-u.ac.jp/sdpa/index.html
i
Key words. Semidefinite programming, interior-point method, computer software, multi-
ple precision arithmetic
∗1 Department of Industrial and Systems Engineering
Chuo University
1-13-27 Kasuga, Bunkyo-ku, Tokyo 112-8551, Japan
∗2 Global Edge Institute
Tokyo Institute of Technology
2-12-1-S6-5 Oh-Okayama, Meguro-ku, Tokyo 152-8550, Japan
∗3 Center for Logistics Research
National Maritime Research Institute
6-38-1 Shinkawa, Mitaka-shi, Tokyo 181-0004, Japan
∗4 Department of Mathematical and Computing Sciences
Tokyo Institute of Technology
2-12-1-W8-29 Oh-Okayama, Meguro-ku, Tokyo 152-8552, Japan
∗5 Department of Industrial Engineering and Management
Tokyo Institute of Technology
2-12-1-W9-62, Oh-Okayama, Meguro-ku, Tokyo 152-8552, Japan
∗6 Advanced Center for Computing and Communication
RIKEN
2-1 Hirosawa, Wako-shi, Saitama 351-0198, Japan
∗7 Department of Mathematical and Computing Sciences
Tokyo Institute of Technology
2-12-1-W8-29 Oh-Okayama, Meguro-ku, Tokyo 152-8552, Japan
ii
Preface
We are pleased to release a new version 7.1.2 of the SDPA and the SDPA-GMP.
The SDPA 7.1.2 was completely revised from its source code, and there are great performance
improvements on its computational time and memory usage. In particular, it uses and stores less
variables internally, and its overall memory usage is less than half of the previous version. Also
it performs sparse Cholesky factorization when the Schur Complement Matrix is sparse. As a
consequence, the SDPA can efficiently solve SDPs with a large number of block diagonal matrices
or non-negative constraints. Additional, there are some improvements on its numerical stability
due to a better control in the interior-point algorithm.
The differences between this version and the previous version, 6.2.1, are summarized in Sec-
tion 11.
Finally, we also provide the SDPA-GMP to solve SDPs highly accurately utilizing multiple
precision arithmetic via the GMP Library (the GNU Multiple Precision Arithmetic Library).
Note that the SDPA-GMP is typically several hundred times slower than the SDPA. Details of the
SDPA-GMP are summarized in the Appendix.
We hope that the SDPA and the SDPA-GMP support many researches in various fields. We
also welcome any suggestions and comments that you may have. When you want to contact us,
please send an e-mail to the following address.
iii
Contents
1. Build and Installation 1
1.1 Prerequisites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 How to Obtain the Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 How to Build . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.1 Fedora 8 and 9 (i386/x86 64/ppc), Red Hat Enterprise Linux (CentOS) 4,
5 (i386/x86 64) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.2 Ubuntu 7.10 Desktop (i386/x86 64) . . . . . . . . . . . . . . . . . . . . . . 2
1.3.3 Vine Linux 4.2 (i386) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3.4 MacOSX Leopard (Intel/PowerPC) . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.5 MacOSX Tiger (Intel/PowerPC) . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3.6 FreeBSD 6 and 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 How to Install . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Test Run . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.6 Performance Tuning: Optimized BLAS and LAPACK . . . . . . . . . . . . . . . . 5
1.6.1 Configure Options . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6.2 Linking Against ATLAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6.3 Linking Against GotoBLAS . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6.4 Linking Against Intel Math Kernel Library . . . . . . . . . . . . . . . . . . 7
1.7 Performance Tuning: Compiler Options . . . . . . . . . . . . . . . . . . . . . . . . 8
2. Semidefinite Program 8
2.1 Standard Form SDP and Its Dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Example 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Example 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3. Files Necessary to Execute the SDPA 10
4. Input Data File 11
4.1 “example1.dat” — Input Data File of Example 1 . . . . . . . . . . . . . . . . . . . 11
4.2 “example2.dat” — Input Data File of Example 2 . . . . . . . . . . . . . . . . . . . 11
4.3 Format of the Input Data File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4 Title and Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.5 Number of the Primal Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.6 Number of Blocks and the Block Structure Vector . . . . . . . . . . . . . . . . . . 13
4.7 Constant Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4.8 Constraint Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
iv
