DSDP

Authors: S. Benson, Ye
Version: 3.2, 11/2000;
Available: yes, from http://www-unix.mcs.anl.gov/ benson/
Key paper: [2]
Features: Dual scaling potential reduction method, rank-1 constraints, Matlab interface, MPI parallel
Language, Input format: C; SDPA
Error computations: yes
Solves: SDP

The DSDP software package is an implementation of the dual scaling algorithm for SDP. Unlike primal-dual interior point methods, this algorithm uses only the dual solution to generate a step direction. It can generate feasible primal solutions as well, but it saves time and memory if this feature is not used. Many large problems have well structured constraints in the form of low rank matrices or sparse matrices. DSDP explicity accounts for these features by using sparse data structures for the dual matrix and the eigenvalue/eigenvector decomposition of the data matrices. Theoretical convergence results exist for feasible starting points, and strong computational results have been achieved using feasible and infeasible starting points. DSDP initially solves the Schur complement equations using the conjugate residual method, and then it switches to the Cholesky method when the conditioning of the matrix worsens.

Stopping criteria:

$$\vert\langle c, x \rangle - b^T y\vert\ /(\vert b^T y\vert + 1) \leq 10^{-3}$$

$$\Vert\mathcal{A}^* y + z - c\Vert _\infty \leq 10^{-8}$$

or

$$\vert b^T y\vert \geq 10^{8}$$

or

stepsizes less than $10^{-3}$ for more than 10 iterations (dual infeasibility)