next up previous contents index
Next: Dual-Scaling Algorithm Up: DSDP5 User Guide - Previous: Contents   Contents   Index

Conic Programming

The DSDP package uses a dual-scaling algorithm to solve conic optimization problems of the form

\begin{displaymath}%%\begin{equation}
\begin{array}{llllllllll}
(P) \ \ \ & \...
...e } = b_i ,& i=1,\ldots, m,
& & X_j \in K_j,\\
\end{array}
\end{displaymath}


\begin{displaymath}%%\begin{equation}
\begin{array}{lllllllll}
(D)    & \mb...
... = C_{j}, & j=1, \ldots, n_b, & S_j \in K_j, \\
\end{array}
\end{displaymath}

where $K_j$ is a cone, $\langle \cdot , \cdot \rangle$ is the associated inner product, and $b_i$, $y_i$ are scalars. For semidefinite programming each cone $K_j$ is a set of symmetric positive definite matrices, the data $A_{i,j}$ and $C_j$ are symmetric matrices of the same dimension, and the inner product $\langle C , X \rangle := {\rm trace  }C^T X = \sum_{k,l}C_{k,l} X_{k,l} $. In linear programming the cone $K$ is the nonnegative orthant $(\mathbb{R}_{+}^n)$, the data $A_{i}$ and $C$ are vectors of the same dimension, and the inner product $\langle C , X \rangle$ 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. Variables that satisfy the constraints are called feasible, whereas the others are called infeasible.

Provided (P) and (D) both have a feasible point and there exist a strictly feasible point to either them, (P) and (D) have solutions and their objective values are equal. To satisfy these assumptions, DSDP bounds the variables $y$ such that $l \leq y \leq u$ where $l,u \in \mathbb{R}^m$. Furthermore, it uses an auxiliary variable $r$ that represents the infeasibility of (D) and associates it with a penalty parameter $\Gamma$ . The use of the bounds and penalty parameter also allows DSDP to apply a feasible-point algorithm even when $y$ and $S$ are infeasible.

The standard form used by DSDP is given by the following pair of problems:

\begin{displaymath}%%\begin{equation}
\begin{array}{lllcccll}
\vspace{0.25cm}...
...e I_j , X_{j} \rangle } & & & \leq & \Gamma, \\
\end{array}
\end{displaymath}


\begin{displaymath}%%\begin{equation}
\begin{array}{llrcll}
\vspace{0.25cm}
...
...q u_i, & & & i=1,\ldots, m, \\
& & r \geq 0,\\
\end{array}
\end{displaymath}

where $I_j$ is the identity element of $K_j$, and $x^l, x^u \in \mathbb{R}^m$ are paired with the lower and upper bounds on $y$, respectively. The parameters $\Gamma$, $l$, and $u$ are set to penalize infeasiblity in (D) and (P) and force the variables $r$, $x^l$, and $x^u$ to be near zero at the solution. By default, the bounds and the penalty parameter $\Gamma$ are very large. Unbounded and infeasible solutions to either (P) or (D) are determined through examination of the solutions to (PP) and (DD).


next up previous contents index
Next: Dual-Scaling Algorithm Up: DSDP5 User Guide - Previous: Contents   Contents   Index
Steven Benson 2005-02-11