DSDP
|
The DSDP package uses a dual-scaling algorithm to solve conic optimization problems of the form
where is a cone,
is the associated inner product, and
,
are scalars. For semidefinite programming each cone
is a set of symmetric positive definite matrices, the data
and
are symmetric matrices of the same dimension, and the inner product of two
matrices
and
is defined by
. In linear programming the cone
is the nonnegative orthant
, the data
and
are vectors of the same dimension, and the inner product
is the usual vector inner product. Formulation (P) will be referred to as the primal problem, and formulation (D) will be referred to as the dual problem.
DSDP is an implementation of the interior-point dual-scaling algorithm for conic programming. The source code, written entirely in ANSI C, is freely available. The solver can be used as a subroutine library, as a function within the MATLAB environment, or as an executable that reads and writes to files. Initiated in 1997, DSDP has developed into an efficient and robust general purpose solver for semidefinite programming. Although the solver is written with semidefinite programming in mind, it can also be used for linear programming and other constraint cones.
The features of DSDP include:
The package has been used in many applications and tested for efficiency, robustness, and ease of use. Some of the most popular applications of semidefinite programming and linear matrix inequalities are model control, truss topology design, and semidefinite relaxations of combinatorial and global optimization problems. We welcome and encourage further use under the terms of the license included in the distribution.
Download the most recent version of DSDP from the DSDP Homepage.
DSDP was developed by Steve Benson, Yinyu Ye, and Xiong Zhang. Please notify the authors of DSDP of your experiences with it. Your feedback helps us promote our research and futher improve the package.
A complete description of the algorithm and a proof of convergence can be found in Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization, SIAM Journal on Optimization, 10(2), 2000, pp. 443-461.
For implementation details, see a publication submitted to ACM Transactions on Mathematical Software: DSDP5: Software For Semidefinite Programming, Preprint ANL/MCS-P1289-0905, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, September, 2005.
For specific use of the software, consult: DSDP5 User Guide — Software for Semidefinite Programming, Technical Report ANL/MCS-TM-277, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, September, 2005.