Semidefinite Programming

From NEOS

Introduction

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

$\min C \bullet X \; \mbox{subject to} A_k \bullet X = b_k, \; k=1,\ldots,m \; X \geq 0$

where $C, A k$ and $X$ are all symmetric $n \times n$ matrices, $b k$ is a scalar, and the constraint $X \geq 0$ means that X, the unknown matrix, must lie in the closed, convex cone of positive semidefinite. Here, $\bullet$ refers to the standard inner product on the space of symmetric matrices, i.e. for symmetric matrices A and B, $A \bullet B = \mbox{trace}(AB)$ . The dual version of the problem is

$\max b^T y \; \mbox{subject to} \; \sum_{k=1}^m y_k A_k + Z = C, \; Z \geq 0$

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 $n\times n$ 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

$Q = \left\{ (x_0,x_1,\ldots,x_n) \in R^{n+1} | x_0^2 \geq \sum_{i=1}^n x_i^2 \right\}$

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]. For a survey on SDP, see [6].

Interior-Point Algorithms

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

$A_k \bullet X \; = \; b_k, \; k=1, \ldots,m$

$\sum_{k=1}^m y_k A_k + Z \; = \; C$

$X \cdot Z = 0$

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 $μ I$ , where $μ > 0$ 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,6].

Applications

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 $V = \{ v_i \}_{i=1}^n$ and edges $(v_i,v_j) \in E$ with weights $w i j$ . The max-cut problem consists in finding the index set $I \subset \{1,\ldots,n\}$ such that the weight of the edges with one end point in $I$ and the other end point in $V \backslash I$ is maximized. This can be formulated as the following optimization problem:

${(MC)} \quad t := \max_x \frac{1}{2} \sum_{i<j} (1 - x_i x_j), \; x \in \{-1,+1\}^n$

We associate $x i = 1$ with $i \in I$ and $x i = - 1$ otherwise. The max-cut problem is known to be NP-hard. We replace the integer constraints with quadratic constraints of the form $x_i^2 = 1$ and move these constraints to the objective to obtain a Lagrangian relaxation of the form

${(MC-LR)} \quad t(\lambda) := \max_x x^T Q x + \sum_i \lambda_i(1 - x_i^2)$

where Q is a symmetric $n \times n$ matrix and the $λ i$ are Lagrange multipliers. The optimal value of (MC-LR) provides an upper bound for the optimal value of (MC), i.e.

$t \leq t(\lambda)$

In particular, this bound has to hold for the $λ$ that minimizes $t (λ)$ , so we have

$t \leq \min_{\lambda} \; \max_x x^T Q x + \sum_i \lambda_i(1 - x_i^2)$

$= \min_{\lambda} \; \max_x x^T(Q - \mbox{Diag}(\lambda)) x + \lambda^T e$

where e is the vector of all ones and $Diag(λ)$ is a diagonal matrix whose i-th diagonal entry is $λ i$ .

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 $Q - \mbox{Diag}(\lambda) \leq 0$ . 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

$\min \lambda^T e \; \mbox{subject to} \; Q - \mbox{Diag}(\lambda) \leq 0$

whose dual is

$\max Q \bullet X \; \mbox{subject to} \; \mbox{diag}(X) = e, \; X \geq 0$

Here, $diag(X)$ 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,6] and references therein.

Software

Unlike LP, SDP software is still in its infancy, and most codes currently availa ble handle moderate sized problems. Here is a list of some SDP packages:

CSDP
Availability: Public domain.
Source available: Yes.
Synopsis: Callable C code, primal-dual path following method, implements the XZ search direction, Mehtortra predictor-corrector, supports sparse problems.
DSDP
Availability: Public domain
Source available: Yes
Synopsis: Implemented in C and callable as a subroutine library or Matlab Mex function, this solver implements an interior-point method called the dual-scaling direction and carefully exploits sparsity and low rank structure in the data.
Matlab LMI Toolbox
Availability: Proprietary.
Source available: No.
Synopsis: SDP solver tailored specifically for control applications, GUI editor for interactive problem specification.
PENSDP
Availability: Free of charge for research.
Source available: No.
Synopsis: Implemented in C and callable as a subroutine library or Matlab Mex function. Implements a generalized augmented Lagrangian method.
SDPA
Availability: Public domain.
Source available: No.
Synposis: C code, primal-dual path following method, impements several standa rd search directions, Mehrotra predictor-corrector, supports sparse problems, linear alge bra based on the Meschach library.
SDPHA
Availability: Public domain.
Source available: Yes.
Synopsis: Matlab code, solves a homogeneous formulation of SDP, primal-dual pat h following method, Mehrotra predictor-corrector, implements standard search directions.
SDPpack
Availability: Free of charge for research and non-commercial use.
Source available: Yes.
Synopsis: Solves semidefinite-quadratic-linearly constrained problems (mixed cone constraints), Matlab 5.0 code with MEX files, primal-dual path following method , implements XZ ZX search direction, Mehrotra predictor-corrector, specialized routines based on the XZ search direction for diagonally constrained SDP's and Lovasz th eta function. Usable over the internet via the NEOS server (submissions via e-mail, web or the NEOS submission tool).
SDPT3
Availability: Public domain.
Source available: Yes.
Synopsis: Matlab code, primal-dual path following method, implements several st andard search directions, Mehrotra predictor-corrector.
SP
Availability: Public domain.
Source available: Yes.
Synopsis: Matlab with MEX files, primal-dual potential reduction method, callab le from C. See also the related packages SDPSOL, (a parser/solver for SDP) and MAXDET (a package for determinant maximization subject to semidefinite constraints).

References

L. Vandenberghe and S. Boyd, Semidefinite programming. SIAM Review, 38:49-95, 1996.
S. J. Wright, Primal-Dual Interior-Point Methods. SIAM, Philadephia , 1996.
F. Alizadeh, J.-P. A. Haeberly, and M. L. Overton. Primal-dual interior-point algorithms for semidefinite programming: stability, convergence and numerical results. Technical Report 721, Computer Science Department, New York University, June 1996. To appear in SIAM Journal on Optimization.
A. S. Lewis and M. L. Overton, Eigenvalue optimization. Acta Numerica, 5:149-190, 1996.
F. Alizadeh, Interior-point methods in semidefinite programming with app lications to combinatorial optimization. SIAM Journal on Optimization, 5(1):13-51, 1991.
H. Wolkowicz, R. Saigal and L. Vandenberghe, Handbook of Semidefinite Programming. Kluwer Academic Publishers, Boston, MA , 2000.

Semidefinite Programming

From NEOS

Contents

Introduction

Interior-Point Algorithms

Applications

Software

References

Views

Personal tools

Navigation

Search

Toolbox