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.

SDP

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

• From LP to conic problems
• Linear matrix inequalitiesSDP
• Standard forms of SDPs
• Applications
• Exercises