Standard Form

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.

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 such that where .
Furthermore, DSDP bounds the trace of by a penalty parameter . By adding these auxiliary variables and parameters, DSDP solves following pair of problems:

where is the identity element of , and . The variables and correspond to the Lagrangian multipliers of the bounds and . The difference of these variables can be interpreted as the infeasibility in the solution of (P). The positive variable augments the variable so that it is a element of . The parameters , , and bound these auxiliary variables and penalize infeasibility in (D) and (P). By default, the bounds and the penalty parameter are very large to force , , and 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).