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.
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).