Semidefinite programming

In the semidefinite programming ( SDP, also Semidefinite Optimization) optimization problems are studied, whose variables are not vectors, but symmetric matrices. As a side condition requires that these matrices is positive ( or negative) semidefinite, hence the name of the problem arises.

The objective function is linear in many cases, so that the Semidefinite programming can be conceived as an extension of linear optimization. But it can also be non-linear.

Since the set of all positive semidefinite matrices in the vector space of symmetric matrices is a cone (English cone ), you can see the Semidefinite programming described as the branch of conic optimization.

Applications, there is in the area of the convex optimization, the approximation theory, the control theory, and combinatorial optimization in the art.

Problem formulation

In the linear case is the standard formulation for a problem of semidefinite programming:

Subject to the constraints

Where the matrices and the values ​​are fixed. The variable X is also a matrix. means that matrix X is to be positive semi-definite. is an abbreviation for the track ( engl. trace) of the matrix. the amount of the symmetric matrices

Example

If you want to find a symmetric matrix for which the sum of the k largest eigenvalues ​​is as small as possible, one can formulate as a problem of semi-definite programming. Here you minimize a target function, the variable t, of which one calls in a constraint that it is greater or equal to the sum of the k largest eigenvalues ​​of X. This constraint is very difficult to handle, because there is no easy function to be calculated, which indicates the eigenvalues ​​of a matrix, and certainly not in a sorted form. However, one can express the constraint equivalent by the following three conditions:

Where E is the identity matrix, T and s are real variables X and Z are variables matrix. These conditions are mathematically easier to deal with, although they look at first sight difficult. All can be easily computed, since they are linear in the variables. The calculation of the track is easy. To check for positive semidefiniteness for the second and third condition, there are special procedures are then used to solve the problem.