The (linear) semidefinite programming problem (SDP) is essentially an ordinary linear program where the nonnegativity constraint is replaced by a semidefinite constraint on matrix variables. The standard form for the primal problem is
where 
and X are
all symmetric 
matrices, 
is a scalar, and the
constraint 
means that X,
the unknown matrix, must lie in the closed, convex cone of positive semidefinite. Here, 
refers to the standard inner
product on the space of symmetric matrices, i.e. for symmetric matrices A
and B, 
. The dual
version of the problem is
where the dual variable y is an m-vector of Lagrange multipliers
corresponding to the equality constraints in the primal, and Z is a symmetric dual slack matrix.
SDP reduces to LP when all the matrices are diagonal. SDP (indeed, LP too) is a special instance of a more general problem class called conic linear programs, where one seeks to minimize a linear objective function subject to linear constraints and a cone constraint. Both the semidefinite cone (for SDP) and the non-negative orthant (for LP) are homogeneous, self-dual cones - there are only 5 such nonisomorphic categories of cones. Another example of a homogeneous, self-dual cone is the quadratic cone, Q, in n+1 dimensions defined by
which gives rise to quadratically constrained problems.
One of the main aspects in which SDP differs from LP is that the non-negative orthant is a polyhedral cone, whereas the semidefinite cone is not. Thus, developing simplex type algorithms for SDP is a topic of current research. However, it is fairly straightforward to design polynomial time primal-dual interior-point algorithms for these problems. For a tutorial on SDP, see [1].
Interior-point algorithms come in two flavors: (i) potential reduction, and (ii) path-following. Further, an interior-point method can be primal only, dual only, or primal-dual. Primal-dual path-following algorithms are popular and are implemented in many currently available codes.
As with LP, primal-dual algorithms solve SDP by solving the Karush-Kuhn-Tucker (KKT) system
while simultaneously ensuring that the iterates X and Z are symmetric and
strictly positive definite. The last equation is the complementarity condition
for SDP. Primal-dual algorithms use Newton's method to solve a relaxed version of this
system: they replace the right-hand side of the complementarity condition by 
, where 
is a parameter that is driven to zero, and
generate a sequence that exhibits global convergence to a solution, if one exists. Again,
a difference arises with LP in that applying Newton's method to the KKT system usually
results in asymmetric corrections for X. A symmetrization of the complementarity
condition is thus warranted. Different symmetrizations lead to different Newton
corrections (search directions). Once a search direction is computed, a step is taken
along this direction so that the new iterate remains strictly positive definite, and the
value of 
is decreased.
This process is repeated until is sufficiently small. For more details on primal-dual interior-point
methods, see [2, 3].
SDP has many applications, ranging from control theory to structural design. In
particular, many hard optimization problems (with integer constraints) can be relaxed to a
problem with convex quadratic constraints which, in turn, can be formulated as an SDP.
This SDP provides a polynomial time approximation to the original, hard problem. Usually,
approximations from SDP relaxations are better than those from linear programming. We
illustrate our point with one application from graph theory: the max-cut problem
which has been instrumental in the recent surge in SDP research. This application also
shows how SDP arises as a relaxation of a problem using quadratic approximations. Suppose
that G = (V,E; W) is a weighted, undirected graph with
vertices 
and edges 
with weights 
. The max-cut problem
consists in finding the index set 
such that the weight of the edges with one end point in I and the
other end point in 
is
maximized. This can be formulated as the following optimization problem:
We associate 
with 
and 
otherwise. The max-cut problem is known to
be NP-hard. We replace the integer constraints with quadratic constraints of the form 
, move these constraints to
the objective to obtain a Lagrangian relaxation of the form
where Q is a symmetric matrix and the 
are Lagrange multipliers. The optimal value of (MC-LR) provides an upper
bound for the optimal value of (MC), i.e.
In particular, this bound has to hold for the 
that minimizes 
, so we have
where e is the vector of all ones and 
is a diagonal matrix whose i-th
diagonal entry is .
We now note that the inner maximization problem is infinite valued unless the Hessian
of the Lagrangian is negative semidefinite, i.e. we have the hidden semidefinite
constraint 
. Moreover,
once we add this semidefinite constraint to the outer minimization problem, the inner
maximization is attained at x = 0. We have eliminated the x variable and the
maximization part of the problem.
Therefore, the upper bound for MC can be obtained by solving the following SDP
whose dual is
Here, 
is a vector
whose i-th entry is the i-th diagonal entry of the matrix X. This
pair of SDP's can now be solved with a primal-dual interior-point algorithm. For a survey
of some applications of SDP, see [4, 5] and references therein.
Unlike LP, SDP software is still in its infancy, and most codes currently available handle moderate sized problems. Here is a list of some SDP packages:
Up To:
[ OTC Home Page | NEOS Guide | NEOS Server | Optimization Tree ]
Madhu Nayakkankuppam, Henry Wolkowicz,
Last updated 18 August 1997
