Next: Dual-Scaling Algorithm
Up: DSDP5 User Guide -
Previous: Contents
  Contents
  Index
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
.
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.
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
such that
where
. Furthermore,
it uses an auxiliary variable
that represents the infeasibility of (D) and associates
it with a penalty parameter
.
The use of the bounds and penalty parameter
also allows DSDP to apply a feasible-point algorithm even when
and
are infeasible.
The standard form used by DSDP is given by the following pair of problems:
where
is the identity element of
, and
are paired with the lower and upper bounds
on
, respectively. The parameters
,
, and
are set to penalize infeasiblity in (D) and (P) and
force the variables
,
, and
to be near zero at the solution.
By default, the bounds and the penalty parameter
are very large.
Unbounded and infeasible solutions to either (P) or (D) are
determined through examination of the solutions to (PP) and (DD).
Next: Dual-Scaling Algorithm
Up: DSDP5 User Guide -
Previous: Contents
  Contents
  Index
Steven Benson
2005-02-11