SDPA(Semidefinite Programming Algorithms) Official Page

The SDPA Family and How to Choose

We have developed the open source package SDPA and its variants SDPA-M, SDPA-C, SDPARA, and SDPARA-C to solve semidefinite programs efficiently and effectively. Each package has its own features and advantages. You can choose an appropriate software package among the family depending on the structure and size of your SDP problem and the available computing environment. All packages share a common input data format called the (sparse) SDPA format, which is a description of the following standard form primal-dual pair of SDPs.

Standard Form of the Semidefinite Program

• The SDPA is the basic software package.
  It is easy to install, and recommended for first-time users. The SDPA is designed to solve small and medium size SDPs: usually number of variables m < 2,000 and matrix sizes n < 2,000 which also depend on the available hardware. You need not to install the SDPA itself to install other packages of the SDPA family.
• The SDPA-M is a MATLAB version of the SDPA.
  Choose this software package if you prefer to use the SDPA in a MATLAB environment.
• The SDPA-C is designed to solve sparse problem.
  It efficiently solves an SDP which involves not many variables (for instance, m < 2,000) and large size but very sparse data matrices (for instance, n < 20,000 and less than 5% of nonzero density).
• The SDPARA is a parallel version of the SDPA,
  which efficiently solves an SDP with a large number of variables, for instance, m < 20,000 and matrix sizes n < 2,000. A PC cluster or a high performance computer with multiple processors is required.
• The SDPARA-C is a parallel version of the SDPA-C,
  which aims to solve a large-scale SDP with sparse data (for instance, m < 20,000, n < 20,000 and 5% of nonzero density). A PC-cluster or a high performance computer with multiple processors is required.
• The SDPA-GMP, SDPA-QD and SDPA-DD
  are designed for obtain highly accurate solutions, however, which are much slower than the SDPA.
• The SDPA-M is a Python version of the SDPA.
  Choose this software package if you prefer to use the SDPA in a Python environment.

The SDPA (SemiDefinite Programming Algorithm) is a software package for solving SDPs. It is based on the Mehrotra-type predictor-corrector infeasible primal-dual interior-point method. The SDPA handles the standard form SDP and its dual problem stated above. It is implemented in C++ language and utilizes the BLAS (or GotoBLAS, Intel MKL, ATLAS) and LAPACK libraries for matrix computations. The SDPA incorporates dynamic memory allocation and deallocation. Therefore, the maximum size of the SDP problem which can be solved depends on the size of the computer's memory where the SDPA is installed. The SDPA has the following additional features:

1. Callable library for the SDPA functions to be included in your C/C++ programs.
2. Handle block diagonal and sparse matrix data structures.
3. Some information on the infeasibility of SDPs is provided.
4. Efficient methods to compute the search directions exploiting the sparsity of the data matrices are implemented.
5. Sparse or dense Cholesky factorization for the Schur complemetn matrix is automatically selected.
6. Multi-thread computing for computing each element of the Schur complement matrix.

The SDPA-M provides a MATLAB interface for the SDPA. It shares all the features with the SDPA except that no callable library is provided. The SDPA-M can be combined with your programs in a MATLAB environment. The SDPA-M has the following additional features:

1. SeDuMi input format
2. SDPA/SDPARA output file can be loaded onto Matlab in SDPA-M/SeDuMi format (If you have solved SDP via Online solver, the result file can be used on Matlab by this function.)

The SDPA-C (SemiDefinite Programming Algorithm with the positive definite matrix Completion) is a C++ software package which solves SDP problems very efficiently (in computational time and memory) if the data matrices of the SDP are large-scale and sparse. For instance, number of variables m < 2,000, matrix sizes n < 20,000, and 5% of nonzero density. More specifically, the SDPA-C is more efficient when there is a sparse structure in the aggregated sparsity pattern over data matrices. Using the positive definite matrix completion, the SDPA-C stores only the sparse matrices and performs matrix computations which take advantages of the sparse structure. Besides the ATLAS (or BLAS) and LAPACK libraries for matrix computations, it utilizes the METIS and SPOOLES libraries for finding a proper sparse structure of the aggregated sparsity pattern. First, please try on Online solver.
[download from here]

The SDPARA (SemiDefinite Programming Algorithm PARAllel version) is a parallel version of the SDPA written in C++ language. The SDPARA works as a stand-alone software package and solves SDPs in parallel with the help of the MPI (Message Passing Interface) and ScaLAPACK (Scalable LAPACK). However, its functions are not available as a callable library. To install and use the package, we assume that you are familiar with the latest version of the SDPA and the MPICH.
First, please try on Online solver.
[download from here]

The SDPARA-C is a parallel version of the SDPA-C and a variant of SDPARA which incorporates the positive definite matrix completion technique. As the SDPA-C, the following packages need to be installed a priori: ATLAS (or BLAS), ScaLAPACK, METIS, SPOOLES, and MPICH.
First, please try on Online solver.
[download from here]

The SDPA-GMP is an SDP solver based on the SDPA, which is intended to obtain highly accurate solutions by utilizing arbitrary precision arithmetic in the GNU Multiple Precision Arithmetic Library (GMP). The current version of the SDPA-GMP shares the same features with the SDPA except for user settable accuracy usually for extraordinary accurate calculations. Expect for newly added one parameters ``precision'', user experience is the same as the SDPA. Note that the SDPA-GMP is typically several ten or hundred times slower than the SDPA.
[download from here]

The SDPA-P provides a Python interface for the SDPA. It shares all the features with the SDPA except that no callable library is provided. In addition, SDPA-P support

1. Conversion proposed in “Exploiting Sparsity in Linear and Nonlinear Matrix Inequalities via Positive Semidefinite Matrix Completion,”
   Sunyoung Kim, Masakazu Kojima, Martin Mevissen and Makoto Yamashita
   Mathematical Programming B,
   Vol. 129, No. 1, pp. 33--68 (2011),
   DOI:10.1007/s10107-010-0402-6
   
2. SDPA/SDPARA output file can be loaded onto Matlab in SDPA-M/SeDuMi format (If you have solved SDP via Online solver, the result file can be used on Matlab by this function.)