<!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: Standard Form</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><a href="index.html"><span>Main Page</span></a></li>
<li class="current"><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">Standard Form </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.</p>
<p>The convergence of the algorithm assumes that both (P) and (D) have an interior feasible region and the current solutions are elements of the interior. To satisfy these assumptions, DSDP bounds the variables <img class="formulaInl" alt="$y$" src="form_36.png"/> such that <img class="formulaInl" alt="$l \leq y \leq u$" src="form_37.png"/> where <img class="formulaInl" alt="$l,u \in \Re^m$" src="form_38.png"/>. Furthermore, DSDP bounds the trace of <img class="formulaInl" alt="$X$" src="form_39.png"/> by a penalty parameter <img class="formulaInl" alt="$\Gamma$" src="form_40.png"/>. By adding these auxiliary variables and parameters, DSDP solves following pair of problems: </p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \begin{array}{llccccll} \vspace{0.25cm} (PP) & \mbox{minimize} & {\displaystyle \sum_{j=1}^{n_b} \langle C_j, X_j \rangle } & + & u^T x^u - l^T x^l \\ &\mbox{subject to}& {\displaystyle \sum_{j=1}^{n_b} \langle A_{i,j}, X_{j} \rangle} & + & x^u_i - x^l_i & = & b_i ,& i=1,\ldots, m, \\ & & {\displaystyle \sum_{j=1}^{n_b} \langle I_j , X_{j} \rangle } & & & \leq & \Gamma, \\ & & X_j \in K_j, & & x^u, x^l & \geq & 0, \\ \end{array} \]" src="form_41.png"/>
</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ \begin{array}{llrcll} \vspace{0.25cm} (DD) & \mbox{maximize} & {\displaystyle \sum_{i=1}^m b_i \ y_i - \Gamma r} \\ & \mbox{subject to}&{\displaystyle C_{j} - \sum_{i=1}^m A_{i,j}y_i + r I_j } & = & S_{j} \in K_j, & j=1, \ldots, n_b, \\ & & l_i \leq y_i \leq u_i, & & & i=1,\ldots, m, \\ & & r \geq 0, \\ \end{array} \]" src="form_42.png"/>
</p>
<p> where <img class="formulaInl" alt="$I_j$" src="form_43.png"/> is the identity element of <img class="formulaInl" alt="$K_j$" src="form_24.png"/>, and <img class="formulaInl" alt="$x^l, x^u \in \Re^m $" src="form_44.png"/> . The variables <img class="formulaInl" alt="$x^l$" src="form_45.png"/> and <img class="formulaInl" alt="$x^u$" src="form_46.png"/> correspond to the Lagrangian multipliers of the bounds <img class="formulaInl" alt="$l$" src="form_47.png"/> and <img class="formulaInl" alt="$u$" src="form_48.png"/>. The difference of these variables can be interpreted as the infeasibility in the solution of (P). The positive variable <img class="formulaInl" alt="$r$" src="form_49.png"/> augments the variable <img class="formulaInl" alt="$S_{j}$" src="form_50.png"/> so that it is a element of <img class="formulaInl" alt="$K_{j}$" src="form_51.png"/>. The parameters <img class="formulaInl" alt="$\Gamma$" src="form_40.png"/>, <img class="formulaInl" alt="$l$" src="form_47.png"/>, and <img class="formulaInl" alt="$u$" src="form_48.png"/> bound these auxiliary variables and penalize infeasibility in (D) and (P). By default, the bounds and the penalty parameter <img class="formulaInl" alt="$\Gamma$" src="form_40.png"/> are very large to force <img class="formulaInl" alt="$r$" src="form_49.png"/>, <img class="formulaInl" alt="$x^l$" src="form_45.png"/>, and <img class="formulaInl" alt="$x^u$" src="form_46.png"/> to be near zero at the solution. Unbounded and infeasible solutions to either (P) or (D) are determined through examination of the solutions to (PP) and (DD). Note that the reformulation (PP) and (DD) is bounded and feasible, and it can be expressed in the form of (P) and (D). </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>
