DSDP

Introduction

DSDP is an open-source sparse SDP solver developed by Steve Benson, Yinyu Ye and Xiong Zhang. DSDP implements a dual-scaling variant of the interior point method, whcih makes better use of the sparsity and the low-rank structure of the problems and has lower memory requirement compared to other interior point algorithms. Currently DSDP solves both LP and SDP instances and has been widely applied to linear matrix inequalities (LMI), model control, truss design and solution to SDP relaxation of combinatorial problems.

Parameters

DSDP Contains logging and algorithmic parameters including

Logging

Parameter <default> Type Explanation
print <10> IntParam Print information at each k iteration
dloginfo <0> IntParam Print more information for higher numbers
dlogsummary <1> IntParam Print timing information
help N/A For help message

Algorithmic

Parameter <default> Type Explanation
timelimit <15000> DblParam Algorithm time limit
gaptol <1e-6> IntParam Stop when relative duality gap less than
r0 <-1> DblParam If nonnegative, initialize S by adding this multiple of the identity matrix
penalty <1e10> DblParam Penalize dual infeasibility
boundy <1e7> DblParam Bound for variables y
maxit <200> IntParam Set maximum iterates
zbar <1e10> DblParam Upper bound for dual solution
mu0 <-1> DblParam If positive, set initial barrier parameter
rho <3> DblParam Potential parameter as multiple of dimension
drho <1> DblParam Use dynamic rho strategy
pnormtol <1e30> DblParam Stop only if pnorm less than
reuse <4> IntParam Reuse the Schur Matrix this many times
bigM <0> DblParam If positive, modify algorithm to make dual infeasibility positive with a large associated cost

Examples of Usage

DSDP can either be called using a C subroutine library or be directly applied to solve SDPA instances . e.g., after compiling the source to get the DSDP binary, one can execute

readsdpa filename.dat-s
1

in the command line to invoke the DSDP solver.

  1. DSDP website https://www.mcs.anl.gov/hs/software/DSDP/ (opens new window)

  2. DSDP theory https://epubs.siam.org/sam-bin/dbq/article/32800([] (opens new window))

  3. DSDP implementation https://www.mcs.anl.gov/hs/software/DSDP/dsdp.bib (opens new window)

Last Updated: 05/16/2022