<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<title>DSDP: Interior Point Solver for Semidefinite Programming and Linear Matrix Inequalities</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link href="doxygen.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<!-- Generated by Doxygen 1.7.4 -->
<div id="top">
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td style="padding-left: 0.5em;">
<div id="projectname">DSDP</div>
</td>
</tr>
</tbody>
</table>
</div>
<div id="navrow1" class="tabs">
<ul class="tablist">
<li class="current"><a href="index.html"><span>Main Page</span></a></li>
<li><a href="pages.html"><span>Related Pages</span></a></li>
<li><a href="modules.html"><span>Modules</span></a></li>
<li><a href="annotated.html"><span>Data Structures</span></a></li>
<li><a href="files.html"><span>Files</span></a></li>
<li><a href="dirs.html"><span>Directories</span></a></li>
</ul>
</div>
</div>
<div class="header">
<div class="headertitle">
<div class="title">Interior Point Solver for Semidefinite Programming and Linear Matrix Inequalities </div> </div>
</div>
<div class="contents">
<div class="textblock"><p>The DSDP package uses a dual-scaling algorithm to solve conic optimization problems of the form </p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \begin{array}{llllllllll} (P) \ \ \ & \mbox{minimize} & {\displaystyle \sum_{j=1}^{n_b} \langle C_j, X_j \rangle } &\mbox{subject to}& {\displaystyle \sum_{j=1}^{n_b} \langle A_{i,j}, X_{j} \rangle } = b_i ,& i=1,\ldots, m, & & X_j \in K_j,\\ \end{array} \]" src="form_22.png"/>
</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \begin{array}{lllllllll} (D) \ \ \ & \mbox{maximize} & {\displaystyle \sum_{i=1}^m b_i \ y_i } &\mbox{subject to}&{\displaystyle \sum_{i=1}^m A_{i,j}y_i + S_{j} } = C_{j}, & j=1, \ldots, n_b, & S_j \in K_j, \\ \end{array} \]" src="form_23.png"/>
</p>
<p> where <img class="formulaInl" alt="$K_j$" src="form_24.png"/> is a cone, <img class="formulaInl" alt="$\langle \cdot , \cdot \rangle$" src="form_25.png"/> is the associated inner product, and <img class="formulaInl" alt="$b_i$" src="form_26.png"/>, <img class="formulaInl" alt="$y_i$" src="form_27.png"/> are scalars. For semidefinite programming each cone <img class="formulaInl" alt="$K_j$" src="form_24.png"/> is a set of symmetric positive definite matrices, the data <img class="formulaInl" alt="$A_{i,j}$" src="form_2.png"/> and <img class="formulaInl" alt="$C_j$" src="form_28.png"/> are symmetric matrices of the same dimension, and the inner product of two <img class="formulaInl" alt="$n \times n$" src="form_3.png"/> matrices <img class="formulaInl" alt="$C=(c_{k,l})$" src="form_29.png"/> and <img class="formulaInl" alt="$X=(x_{k,l})$" src="form_30.png"/> is defined by <img class="formulaInl" alt="$\langle C , X \rangle := trace (C^T X) = \sum_{k,l}c_{k,l} x_{k,l} $" src="form_31.png"/>. In linear programming the cone <img class="formulaInl" alt="$K_j$" src="form_24.png"/> is the nonnegative orthant <img class="formulaInl" alt="$(\Re_{+}^n)$" src="form_32.png"/>, the data <img class="formulaInl" alt="$A_{i}$" src="form_33.png"/> and <img class="formulaInl" alt="$C$" src="form_34.png"/> are vectors of the same dimension, and the inner product <img class="formulaInl" alt="$\langle C , X \rangle$" src="form_35.png"/> is the usual vector inner product. Formulation (P) will be referred to as the <em>primal</em> problem, and formulation (D) will be referred to as the <em>dual</em> problem.</p>
<p>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.</p>
<p>The features of DSDP include:</p>
<ul>
<li>a robust algorithm with a convergence proof and polynomially bounded complexity under mild assumptions on the data,</li>
<li>primal and dual solutions,</li>
<li>feasible solutions when they exist or approximate certificates of infeasibity,</li>
<li>initial points that can be feasible or infeasible,</li>
<li>relatively low memory requirements for an interior-point method,</li>
<li>sparse and low-rank data structures,</li>
<li>extensibility that allows applications to customize the solver and improve its performance,</li>
<li>a subroutine library that enables it to be linked to larger applications,</li>
<li>scalable performance for large problems on parallel architectures, and</li>
<li>a well documented interface and examples of its use.</li>
</ul>
<p>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.</p>
<h2><a class="anchor" id="Download"></a>
Download</h2>
<p>Download the most recent version of DSDP from the <a href="http://www.mcs.anl.gov/~benson/dsdp/index.html">DSDP Homepage</a>.</p>
<h2><a class="anchor" id="authors"></a>
Authors</h2>
<p>DSDP was developed by <a href="http://www.mcs.anl.gov/~benson/">Steve Benson</a>, <a href="http://www.stanford.edu/~yyye/">Yinyu Ye</a>, 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.</p>
<h2><a class="anchor" id="References"></a>
References</h2>
<p>A complete description of the algorithm and a proof of convergence can be found in <a href="http://epubs.siam.org/sam-bin/dbq/article/32800">Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization</a>, SIAM Journal on Optimization, 10(2), 2000, pp. 443-461. </p>
<p>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. </p>
<p>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. </p>
</div></div>
<hr class="footer"/><address class="footer"><small>Generated on Wed Jun 8 2011 for DSDP by 
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.7.4 </small></address>
</body>
</html>
