Semidefinite programming

Subfield of convex optimization
Semidefinite programming (SDP) is a subfield of mathematical programming concerned with the optimization of a linear objective function (a user specified function that the user wants to minimize or maximize)
over the intersection of the cone of positive semidefinite matrices with an affine space, i. e., a spectrahedron. 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 or approximated as semidefinite programming problems. In automatic control theory, SDPs are used in the context of linear matrix inequalities. SDPs are in fact a special case of cone programming and can be efficiently solved by interior point methods. All linear programs and (convex) quadratic programs can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated. Semidefinite programming has been used in the optimization of complex systems. In recent years, some quantum query complexity problems have been formulated in terms of semidefinite programs.

A linear programming problem is one in which we wish to maximize or minimize a linear objective function of real variables over a polytope. In semidefinite programming, we instead use real valued vectors and are allowed to take the dot product of vectors; nonnegativity constraints on real variables in LP (linear programming) are replaced by semidefiniteness constraints on matrix variables in SDP (semidefinite programming). Specifically, a general semidefinite programming problem can be defined as any mathematical programming problem of the form

where the , and the are real numbers and is the dot product of and .

The space of semidefinite matrices is a convex cone. Therefore, SDP is a special case of conic optimization, which is a special case of convex optimization. When the matrix C is diagonal, the inner products <C,X> is equivalent to a vector product of the diagonal of C and the diagonal of X. Analogously, when the matrices Ak are diagonal, the corresponding inner products are equivalent to vector products. In these vector products, only the diagonal elements of X are used, so we can add constraints equating the non diagonal elements of X to 0. The condition is then equivalent to the condition that all diagonal elements of X are non negative. Then, the resulting SDP becomes a linear program in which the variables are the diagonal elements of X.

The weak duality theorem states that the value of the primal SDP is at least the value of the dual SDP. Therefore, any feasible solution to the dual SDP lower bounds the primal SDP value, and conversely, any feasible solution to the primal SDP upper bounds the dual SDP value. This is because

where the last inequality is because both matrices are positive semidefinite, and the result of this function is sometimes referred to as duality gap.

Consider three random variables , , and A given set of correlation coefficients are possible if and only if

This matrix is called the correlation matrix. Suppose that we know from some prior knowledge (empirical results of an experiment, for example) that and The problem of determining the smallest and largest values that can take is given by:

We set to obtain the answer. This can be formulated by an SDP. We handle the inequality constraints by augmenting the variable matrix and introducing slack variables, for example

Solving this SDP gives the minimum and maximum values of as and respectively.

Semidefinite programs are important tools for developing approximation algorithms for NP hard maximization problems. The first approximation algorithm based on an SDP is due to Michel Goemans and David P. Williamson (JACM, 1995).

Semidefinite programming has been applied to find approximate solutions to combinatorial optimization problems, such as the solution of the max cut problem with an approximation ratio of 0.87856. SDPs are also used in geometry to determine tensegrity graphs, and arise in control theory as LMIs, and in inverse elliptic coefficient problems as convex, non linear, semidefiniteness constraints. It is also widely used in physics to constrain conformal field theories with the conformal bootstrap.

The semidefinite feasibility problem (SDF) is the following decision problem: given an SDP, decide whether it has at least one feasible solution. The exact run time complexity of this problem is unknown (as of 1997). However, Ramana proved the following: are based on this approach.

First order methods for conic optimization avoid computing, storing and factorizing a large Hessian matrix and scale to much larger problems than interior point methods, at some cost in accuracy. A first order method is implemented in the Splitting Cone Solver (SCS). Another first order method is the alternating direction method of multipliers (ADMM). This method requires in every step projection on the cone of semidefinite matrices.

The code ConicBundle formulates the SDP problem as a nonsmooth optimization problem and solves it by the Spectral Bundle method of nonsmooth optimization. This approach is very efficient for a special class of linear SDP problems.

Algorithms based on Augmented Lagrangian method (PENSDP) are similar in behavior to the interior point methods and can be specialized to some very large scale problems. Other algorithms use low rank information and reformulation of the SDP as a nonlinear programming problem (SDPLR, ManiSDP).

Algorithms that solve SDPs approximately have been proposed as well. The main goal of such methods is to achieve lower complexity in applications where approximate solutions are sufficient and complexity must be minimal. A prominent method that has been used for data detection in multiple input multiple output (MIMO) wireless systems is Triangular Approximate SEmidefinite Relaxation (TASER), which operates on the Cholesky decomposition factors of the semidefinite matrix instead of the semidefinite matrix. This method calculates approximate solutions for a max cut like problem that are often comparable to solutions from exact solvers but in only 10 20 algorithm iterations. Hazan has developed an approximate algorithm for solving SDPs with the additional constraint that the trace of the variables matrix must be 1.