Semidefinite programming

Semidefinite programming (SDP) is a subfield of convex optimization 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 (SDP) is a subfield of convex optimization 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 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 c i , j , a i , j , k {displaystyle c_{i,j},a_{i,j,k}} , and the b k {displaystyle b_{k}} are real numbers and x i ⋅ x j {displaystyle x^{i}cdot x^{j}} is the dot product of x i {displaystyle x^{i}} and x j {displaystyle x^{j}} . An n × n {displaystyle n imes n} matrix M {displaystyle M} is said to be positive semidefinite if it is the Gramian matrix of some vectors (i.e. if there exist vectors x 1 , … , x n {displaystyle x^{1},ldots ,x^{n}} such that m i , j = x i ⋅ x j {displaystyle m_{i,j}=x^{i}cdot x^{j}} for all i , j {displaystyle i,j} ). If this is the case, we denote this as M ⪰ 0 {displaystyle Msucceq 0} . Note that there are several other equivalent definitions of being positive semidefinite, for example, positive semidefinite matrices are self-adjoint matrices that have only non-negative eigenvalues. Denote by S n {displaystyle mathbb {S} ^{n}} the space of all n × n {displaystyle n imes n} real symmetric matrices. The space is equipped with the inner product (where t r {displaystyle { m {tr}}} denotes the trace) ⟨ A , B ⟩ S n = t r ( A T B ) = ∑ i = 1 , j = 1 n A i j B i j . {displaystyle langle A,B angle _{mathbb {S} ^{n}}={ m {tr}}(A^{T}B)=sum _{i=1,j=1}^{n}A_{ij}B_{ij}.}