Optimization Models
Home
Software
Links
Index
Contact
1. Introduction
1.1. Overview
1.2. Optimization Models
2. Linear Algebra
2.1. Vectors
2.2. Matrices
2.3. Linear Equations
2.4.  Least-Squares
2.5. Eigenvalues
2.6  Singular Values
3. Convex Models
3.1. Convexity
3.2. LP and QP
3.3. SOCP
3.4. Robust LP
3.5. GP
3.6. SDP
3.7. Non-Convex Models
4. Duality
4.1. Weak Duality
4.2. Strong Duality
4.3.  Applications
5. Case Studies
5.1. Senate Voting
5.2. Antenna Arrays
5.3. Localization
5.4. Circuit Design

Semidefinite Programming

Semidefinite programming (SDP) is an optimization model where the objective is linear, and the constraints involve affine combinations of symmetric matrices that are required to be positive semi-definite. SDPs include as special cases LPs, when all the symmetric matrices involved are diagonal; and SOCPs, when the symmetric matrices have a special ‘‘arrow’’ form. General SDPs are perhaps one of the most powerful forms of convex optimization.

alt text 

SDPs arise in a wide range of applications. For example, they can be used as sophisticated relaxations (approximations) of non-convex problems, such as boolean problems with quadratic objective. They are also useful in the context of analyzing the stability, or more generally, the time-behavior, of linear dynamical systems subject to perturbations. They can also allow to solve data visualization problems, in particular those where sparsity constraints are imposed on the vectors on which the data is projected.

The image shows a graph showing similarities between musicians based on Yahoo! music data. A method based on semidefinite programming, known as maximum variance unfolding, was used to represent the similarity data in two dimensions.

Outline