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 the sum of squares hierarchy of SDPs can approximate the solutions of polynomial optimization problems. 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.
Motivation and definition
Initial motivation 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
min x 1 , … , x n ∈ R n ∑ i , j ∈ [ n ] c i , j ( x i ⋅ x j ) subject to ∑ i , j ∈ [ n ] a i , j , k ( x i ⋅ x j ) ≤ b k for all k {\displaystyle {\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}&{\displaystyle \sum _{i,j\in [n]}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{subject to}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}}{\text{ for all }}k\\\end{array}}}
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}} .
… excerpt ends here. Continue reading the full article.
