Semidefinite programming (SDP) is an area of mathematics concerned with special optimization problems: the optimization of a linear objective function over the intersection of the cone of positive semidefinite matricies with an affine space. In linear algebra, a positive-definite matrix is a Hermitian matrix which in many ways is analogous to a positive real number. ... In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, of elements of a ring-like algebraic structure. ... In mathematics, an affine space is an abstract structure that generalises the affine-geometric properties of Euclidean space. ...

Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled as semidefinite programming problems. Moreover, as a set of subproblems, SDP covers linear programming and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Finally, semidefinite programming can aid in the design of quantum computing circuits, which makes it interesting as a future subject. Operations research, operational research, or simply OR, is the use of mathematical models, statistics and algorithms to aid in decision-making. ... Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ... In mathematics, linear programming (LP) problems are optimization problems in which the objective function and the constraints are all linear. ... Molecule of alanine used in NMR implementation of error correction. ...

Definition

Standard form

The standard form is the usual form writing a semidefinite programming problem.
It consists of the following three parts :

• A linear function to be maximized

e.g. maximize

• Some linear problem constraints

e.g.

• semi-definteness of the variable-matrix

e.g.

Here in the last line "" stands for positive semidefinite. In linear algebra, a positive-definite matrix is a Hermitian matrix which in many ways is analogous to a positive real number. ...

Using the so called trace product, a scalar product for matricies, i.e., < A,B > : = tr(A^* B), the problem is usually expressed in matrix form: In linear algebra, the trace of an n-by-n square matrix A is defined to be the sum of the elements on the main diagonal (the diagonal from the upper left to the lower right) of A, i. ... In mathematics, a matrix (plural matrices) is a rectangular table of numbers or, more generally, of elements of a ring-like algebraic structure. ...

maximize

subject to

,

,

,

where is positive semidefinite.

In linear algebra, a positive-definite matrix is a Hermitian matrix which in many ways is analogous to a positive real number. ...

Duality

Example

Algorithms

Interior point methods

Bundle method

Applications

Open problems

See also

References

External links

• Christoph Helmberg's page giving links to introductions and events in the field

Software

• Christoph Helmberg's overview over existing software.
• SeDuMi: (Self-Dual-Minimization) solves optimization problems over symmetric cones (this includes semidefinite optimization).