SDPA

Authors: Fujisawa, Kojima, Nakata
Version 5.02, 9/2000; Available: yes; the software manual and the SDPA source codes can be found at http://www.is.titech.ac.jp/ yamashi9/sdpa/index.html
Key paper: [11]. For implementation and numerical results - [9].
Features: primal-dual method, tested version uses Meschach library
Language, Input format: C++; SDPA
Error computations: yes
Solves: SDP

The SDPA (SemiDefinite Programming Algorithm) is based on a Mehrotra-type predictor-corrector infeasible primal-dual interior-point method [17,9], and is implemented in the C++ language utilizing the Meschach [23] library for matrix computations. The main features are: it is available in a callable library, three types of search directions can be used (H..K..M, NT and AHO), block diagonal and sparse data matrix structures are exploited, and information on infeasibility is provided. SDPA uses a set of parameters which the user can adjust to cope with numerically difficult semidefinite programs.

Stopping criteria:

• $\min \{ \left \Vert\mathcal{A}x - b\Vert _\infty,\Vert\mathcal{A}^* y + z - c\Vert _\infty \right \} \leq \epsilon'$ and
• $\frac{\vert\langle c, x \rangle - b^T y\vert}{\max \left \{(\vert\langle c, x \rangle \vert + \vert b^T y\vert)\vert/2.0, 1.0 \right \} } \leq \epsilon^*$

Typical values of the parameters $\epsilon'$ and $\epsilon^*$ are $10^{-6} \sim 10^{-8}$. See [9,11] for more details.