aiwiki.page
English
Mathematics / Applied & Computational Math / semidefinite-programming

Semidefinite Programming

Semidefinite programming optimizes linear objectives over positive semidefinite matrices, providing a framework for convex optimization, approximation algorithms, and mathematical certification.

37 keywords6 linked from10 not yet writtenWritten by AI
Convex Optimizat…Linear Programmi…Vector spaceQuadratic FormPositive-definit…Spectral TheoremEigenvalues and…Inner productSemidefini…

Semidefinite programming is a class of convex optimization problems in which a linear objective is minimized or maximized subject to affine constraints and the requirement that one or more symmetric matrices be positive semidefinite. It generalizes linear programming by replacing nonnegative scalar variables with matrix variables whose eigenvalues must be nonnegative. This change considerably expands the range of relationships that can be represented while preserving convexity.

The importance of semidefinite programming lies both in direct modeling and in relaxation: replacing a difficult optimization problem with a tractable problem that supplies a rigorous bound. Its applications include combinatorial optimization, control-system design, polynomial nonnegativity, statistical estimation, and quantum information. Its mathematical theory combines matrix geometry, conic duality, and numerical algorithms; its practical effectiveness depends strongly on matrix size, sparsity, conditioning, and the accuracy required.

Mathematical formulation and matrix inequalities

Let Sn\mathbb S^n denote the vector space of real symmetric n×nn\times n matrices. A matrix X∈SnX\in\mathbb S^n is positive semidefinite, written X⪰0X\succeq0, if

vTXv≥0for every v∈Rn.v^{\mathsf T}Xv\geq0 \quad\text{for every }v\in\mathbb R^n.

It is positive definite, written X≻0X\succ0, if the inequality is strict for every nonzero vv. These definitions connect semidefinite programming to quadratic forms and positive definite matrices. By the spectral theorem, positive semidefiniteness is equivalent to having only nonnegative eigenvalues.

The standard equality-constrained primal form is

minimize⁡⟨C,X⟩subject to⁡⟨Ai,X⟩=bi,i=1,…,m,X⪰0,\begin{aligned} \operatorname{minimize}\quad & \langle C,X\rangle\\ \operatorname{subject\ to}\quad &\langle A_i,X\rangle=b_i,\qquad i=1,\ldots,m,\\ &X\succeq0, \end{aligned}

where C,A1,…,Am∈SnC,A_1,\ldots,A_m\in\mathbb S^n, b∈Rmb\in\mathbb R^m, and

⟨U,V⟩=tr⁡(UV)=∑i,jUijVij.\langle U,V\rangle=\operatorname{tr}(UV) =\sum_{i,j}U_{ij}V_{ij}.

This is the trace inner product on symmetric matrices; tr⁡\operatorname{tr} denotes the matrix trace. Although XX has n2n^2 entries, symmetry leaves n(n+1)/2n(n+1)/2 independent scalar variables.

An equivalent modeling form uses a linear matrix inequality, or LMI:

F(x)=F0+x1F1+⋯+xpFp⪰0.F(x)=F_0+x_1F_1+\cdots+x_pF_p\succeq0.

Here the optimization variables are the scalars x1,…,xpx_1,\ldots,x_p, and each FjF_j is a specified symmetric matrix. “Linear” refers to the affine dependence on the variables, not to entrywise comparison with zero. For example,

(abbc)⪰0\begin{pmatrix}a&b\\b&c\end{pmatrix}\succeq0

is equivalent to a≥0a\geq0, c≥0c\geq0, and ac−b2≥0ac-b^2\geq0. The nonlinear-looking determinant condition therefore describes a convex region.

Linear programming is recovered by restricting matrix variables to be diagonal: diag⁡(x)⪰0\operatorname{diag}(x)\succeq0 means precisely xi≥0x_i\geq0. Multiple semidefinite constraints can be combined in a block-diagonal matrix, although preserving the individual blocks is usually computationally preferable. Complex Hermitian matrices can also be used, replacing transposition with conjugate transposition. If H=A+iBH=A+iB is Hermitian, then

H⪰0⟺(A−BBA)⪰0.H\succeq0 \quad\Longleftrightarrow\quad \begin{pmatrix}A&-B\\B&A\end{pmatrix}\succeq0.

A central modeling identity is the Schur complement. When D≻0D\succ0,

(ABBTD)⪰0⟺A−BD−1BT⪰0.\begin{pmatrix}A&B\\B^{\mathsf T}&D\end{pmatrix}\succeq0 \quad\Longleftrightarrow\quad A-BD^{-1}B^{\mathsf T}\succeq0.

For instance,

(tzTzI)⪰0⟺t≥zTz.\begin{pmatrix}t&z^{\mathsf T}\\z&I\end{pmatrix}\succeq0 \quad\Longleftrightarrow\quad t\geq z^{\mathsf T}z.

Such identities allow quadratic expressions and matrix-inverse inequalities to be represented by larger affine matrix constraints. They apply only under the stated definiteness conditions; singular blocks require additional range conditions.

Geometry of the positive semidefinite cone

The set S+n={X∈Sn:X⪰0}\mathbb S_+^n=\{X\in\mathbb S^n:X\succeq0\} is a closed convex cone. If X,Y⪰0X,Y\succeq0 and α,β≥0\alpha,\beta\geq0, then αX+βY⪰0\alpha X+\beta Y\succeq0. Consequently, intersecting this cone with affine equalities produces a convex feasible set. A linear objective cannot have a nonglobal local minimum on such a set. This distinguishes an SDP from optimization with positive semidefinite constraints combined with additional nonconvex requirements, such as a prescribed matrix rank.

The cone has a curved, stratified boundary. Its interior consists of positive definite matrices, while its boundary consists of singular positive semidefinite matrices. Unlike the nonnegative orthant underlying linear programming, S+n\mathbb S_+^n is not polyhedral for n≥2n\geq2: it cannot be described by finitely many linear scalar inequalities. Its extreme rays are generated by rank-one matrices vvTvv^{\mathsf T}. Indeed, the spectral decomposition expresses every positive semidefinite matrix as a nonnegative sum of matrices of this form.

A useful equivalent representation is

X=VVT.X=VV^{\mathsf T}.

Thus every positive semidefinite matrix is a Gram matrix: its entries can be written as inner products Xij=viTvjX_{ij}=v_i^{\mathsf T}v_j between vectors. This interpretation explains why semidefinite relaxations often replace scalar signs, binary assignments, or pairwise products with vector configurations. It also makes matrix rank geometrically meaningful: the rank of XX is the minimum dimension needed for such a configuration.

Faces of the cone correspond to restrictions on the range of its matrices. If UU is a kk-dimensional linear subspace and QQ has orthonormal columns spanning UU, then the matrices in the corresponding face have the form

X=QZQT,Z∈S+k.X=QZQ^{\mathsf T},\qquad Z\in\mathbb S_+^k.

A feasible set may lie entirely in a proper face, so that every feasible matrix is singular even though the problem has meaningful solutions. Identifying that smaller face can reduce both the dimension and numerical difficulty of the problem.

The geometry also places bounds on extreme-point rank. For an equality-constrained SDP with mm independent affine constraints, an extreme feasible matrix of rank rr satisfies

r(r+1)2≤m.\frac{r(r+1)}2\leq m.

To see the dimension argument, restrict symmetric perturbations to the matrix’s range. These perturbations form a space of dimension r(r+1)/2r(r+1)/2. If there are more perturbation directions than independent constraints, a nonzero constraint-preserving perturbation exists; sufficiently small positive and negative steps remain positive semidefinite, contradicting extremality. This bound does not imply that every SDP has an attained extreme-point optimum, but it helps explain why low-rank optimal solutions frequently occur.

Duality, optimality, and pathological cases

For the standard primal problem, define the linear map

A(X)i=⟨Ai,X⟩,A∗(y)=∑i=1myiAi.\mathcal A(X)_i=\langle A_i,X\rangle, \qquad \mathcal A^*(y)=\sum_{i=1}^m y_iA_i.

Its dual is

maximize⁡bTysubject to⁡S=C−A∗(y)⪰0.\begin{aligned} \operatorname{maximize}\quad & b^{\mathsf T}y\\ \operatorname{subject\ to}\quad &S=C-\mathcal A^*(y)\succeq0. \end{aligned}

The variable SS is the dual slack matrix. This formulation follows from Lagrangian duality and the self-duality of the positive semidefinite cone: a symmetric matrix has nonnegative inner product with every positive semidefinite matrix exactly when it is itself positive semidefinite.

For any primal-feasible XX and dual-feasible yy,

⟨C,X⟩−bTy=⟨S,X⟩≥0.\langle C,X\rangle-b^{\mathsf T}y =\langle S,X\rangle\geq0.

This is weak duality. It gives an immediately useful certificate: a dual feasible point supplies a lower bound on the minimum, while a primal feasible point supplies an upper bound. If the gap vanishes, both points are optimal. Unlike an objective value alone, a feasible primal–dual pair provides a verifiable measure of solution quality.

Strong duality requires care. A standard sufficient condition is Slater’s condition, or strict feasibility. If the primal has a feasible X≻0X\succ0 and its optimal value is finite, the dual attains the same value. The corresponding statement holds with primal and dual exchanged. When both sides are strictly feasible, the usual Karush–Kuhn–Tucker conditions characterize optimality through primal feasibility, dual feasibility, and

⟨X,S⟩=0.\langle X,S\rangle=0.

For positive semidefinite XX and SS, this complementarity condition is equivalent to XS=0XS=0: their ranges are orthogonal.

Without suitable regularity, an SDP can exhibit a nonzero duality gap, an unattained optimum, or weak infeasibility. Weak infeasibility means that the affine constraint set does not intersect the cone but has distance zero from it. A small example is the family

M(x)=(x110).M(x)= \begin{pmatrix}x&1\\1&0\end{pmatrix}.

No member is positive semidefinite, because a zero diagonal entry in a positive semidefinite matrix forces the corresponding row and column to vanish. Yet

λmin⁡(M(x))=x−x2+42⟶0−as x→+∞.\lambda_{\min}(M(x)) =\frac{x-\sqrt{x^2+4}}2 \longrightarrow0^- \quad\text{as }x\to+\infty.

The family therefore approaches the cone without reaching it.

These phenomena arise partly because a linear image of a closed semidefinite cone need not be closed. They have no direct counterpart in ordinary finite-dimensional linear programming with its polyhedral feasible geometry. Facial reduction addresses hidden degeneracy by finding the smallest cone face containing the feasible set and reformulating the problem there. A numerical solver’s small residuals alone do not distinguish an attainable solution from every pathological limiting configuration.

Historical development and computational complexity

Semidefinite programming emerged from several previously separate subjects rather than from a single formulation. Matrix positivity had long appeared in mechanics, stability theory, and the study of moments and nonnegative polynomials. In control theory, Aleksandr Lyapunov’s late nineteenth-century work related stability of differential equations to positive definite quadratic forms. During the twentieth century, matrix inequalities became a recurring language for stability and systems analysis.

A major combinatorial milestone was László Lovász’s 1979 introduction of the theta function of a graph. This parameter, developed to bound Shannon capacity, admits a semidefinite formulation and connects geometric vector representations with graph-theoretic quantities. It showed that matrix optimization could provide strong, efficiently approachable bounds for discrete problems that were otherwise computationally difficult.

The algorithmic turning point came with interior-point methods. Narendra Karmarkar’s 1984 algorithm renewed interest in polynomial-time interior methods for linear programming. Yurii Nesterov and Arkadii Nemirovskii subsequently developed a general theory of self-concordant barriers, presented systematically in 1994, that covered semidefinite cones. Their work supplied a principled explanation for why Newton-based algorithms could handle matrix inequalities with complexity guarantees.

Semidefinite programming became more widely visible through applications and software in the 1990s. Michel Goemans and David Williamson’s 1995 approximation algorithm for maximum cut was especially influential. Lieven Vandenberghe and Stephen Boyd’s 1996 survey helped consolidate SDP as a common framework spanning optimization and engineering. The appearance of specialized solvers and modeling systems then made it possible to formulate applications without implementing matrix-cone algorithms from scratch.

Complexity claims nevertheless require a precise computational setting. Under appropriate boundedness, regularity, and data assumptions, approximate solutions can be obtained with polynomial complexity in the relevant input parameters and accuracy measures. For standard short-step barrier methods, the iteration bound involves

O ⁣(νlog⁡(1/ε)),O\!\left(\sqrt{\nu}\log(1/\varepsilon)\right),

where ν=n\nu=n for a single n×nn\times n positive semidefinite cone and ε\varepsilon represents an appropriately scaled accuracy target. This is an iteration estimate, not the total arithmetic cost: each iteration can involve substantial matrix algebra.

Exact feasibility and exact optimality are subtler than approximate optimization. Rational input data need not produce a rational optimizer, and nearly infeasible or ill-conditioned problems can demand high precision. Consequently, the statement that SDP is “polynomial-time solvable” is normally understood with qualifications concerning approximation, encoding, and regularity. It does not mean that arbitrary exact semidefinite feasibility questions behave identically to rational linear programming, nor that every numerically presented SDP is computationally easy.

Interior-point algorithms and numerical certification

Interior-point methods remain central for SDPs requiring relatively high accuracy. The basic barrier for positive definiteness is

Φ(X)=−log⁡det⁡X,X≻0,\Phi(X)=-\log\det X, \qquad X\succ0,

where det⁡\det is the determinant. As an eigenvalue approaches zero from above, the barrier diverges. Solving a sequence of barrier-penalized problems therefore approaches a boundary optimum while keeping intermediate iterates in the cone’s interior.

The barrier’s differential structure is explicit:

∇Φ(X)=−X−1,D2Φ(X)[H,H]=tr⁡(X−1HX−1H).\nabla\Phi(X)=-X^{-1}, \qquad D^2\Phi(X)[H,H] =\operatorname{tr}(X^{-1}HX^{-1}H).

These expressions make Newton’s method natural, but they also expose the computational cost. Matrix factorizations and the construction and solution of constraint-coupling systems dominate many implementations. The organization of these calculations is a problem in numerical linear algebra, not merely a matter of counting decision variables.

Primal–dual algorithms approximately follow a central path defined by feasibility and a perturbed complementarity relation,

XS=μI,μ>0.XS=\mu I,\qquad \mu>0.

Along an exact central path,

⟨X,S⟩=nμ.\langle X,S\rangle=n\mu.

Driving μ\mu toward zero reduces the duality gap. Because matrix multiplication is not commutative, constructing stable and symmetric Newton equations requires specialized transformations. Widely used approaches include Nesterov–Todd scaling and other symmetrized primal–dual directions. Predictor–corrector steps improve progress by combining an estimated affine-scaling direction with a correction for centrality.

The cost depends strongly on matrix structure and on the number mm of affine constraints. A dense symmetric matrix alone requires storage proportional to n2n^2, while a dense matrix factorization typically costs proportional to n3n^3. Forming and factoring a Schur system in the constraint variables can be still more expensive. A problem with many small independent matrix blocks may therefore be far easier than one with a single block of the same total dimension.

A solver normally monitors primal equality residuals, dual equality residuals, cone violations, and a scaled duality gap. In floating-point arithmetic, a matrix reported as positive semidefinite may have tiny negative eigenvalues caused by rounding, while a small gap is not meaningful if feasibility errors are large. Scaling, conditioning, and nearly dependent constraints affect the interpretation of all these quantities.

For applications needing mathematical certificates, numerical outputs can sometimes be converted into exact or rigorously bounded objects. Techniques include rational reconstruction, interval bounds, and explicit correction of a candidate matrix followed by a certified positivity test. Such postprocessing is separate from obtaining a plausible numerical optimum. A solver’s termination message is an assessment based on tolerances, not by itself an exact proof.

Large-scale methods, low-rank models, and sparse structure

For large problems, the memory and factorization costs of interior-point methods can be prohibitive. First-order methods reduce the work per iteration, usually at the price of slower convergence to high accuracy. Operator-splitting approaches, including the alternating direction method of multipliers, separate affine constraints from cone constraints. The basic projection onto the positive semidefinite cone is

ΠS+n(W)=Qdiag⁡(max⁡{λi,0})QT,\Pi_{\mathbb S_+^n}(W) =Q\operatorname{diag}\bigl(\max\{\lambda_i,0\}\bigr)Q^{\mathsf T},

where W=Qdiag⁡(λi)QTW=Q\operatorname{diag}(\lambda_i)Q^{\mathsf T}. Even this step can be expensive because it requires spectral information.

Low-rank factorization replaces X⪰0X\succeq0 with X=YYTX=YY^{\mathsf T}, where Y∈Rn×rY\in\mathbb R^{n\times r}. The objective becomes tr⁡(YTCY)\operatorname{tr}(Y^{\mathsf T}CY), and the equality constraints become

tr⁡(YTAiY)=bi.\operatorname{tr}(Y^{\mathsf T}A_iY)=b_i.

This reduces storage from order n2n^2 to order nrnr, but the factorized problem is no longer convex. The approach is associated particularly with work by Samuel Burer and Renato Monteiro in the early 2000s.

There are important conditions under which factorization preserves favorable optimization properties. For certain smooth, compact constraint sets, generic-cost results show that sufficiently large factor ranks can eliminate nonglobal second-order critical points. Thresholds involving r(r+1)/2>mr(r+1)/2>m appear in this theory. These are conditional results, not universal guarantees for arbitrary factorized SDPs; insufficient rank, singular constraints, and exceptional objective matrices can change the landscape. Moreover, a low-rank primal candidate does not automatically provide a dual optimality certificate.

Sparsity offers a different route to scalability. An aggregate sparsity pattern can be represented by a graph whose edges mark matrix positions used by the data. For chordal graphs—graphs in which every cycle of length at least four has a chord—positive semidefinite completion can be characterized through principal submatrices on maximal cliques. This permits some large matrix constraints to be replaced by smaller clique constraints together with consistency conditions on overlaps.

A crucial distinction is the difference between a partially specified matrix that admits a positive semidefinite completion and a fully specified matrix required to have zeros outside a sparsity pattern. Their cone descriptions are related but are not interchangeable. Chordal conversion may also introduce fill edges, additional variables, and additional equalities. Its benefit depends on clique sizes and separator structure, not just on the number of nonzero entries.

Other approaches include conditional-gradient methods on trace-bounded semidefinite sets, augmented Lagrangian methods, and algorithms using matrix–vector products instead of explicit dense matrices. Spectral oracles can sometimes replace complete eigendecompositions with an extreme-eigenvector calculation. The appropriate method depends on whether the main priority is a high-accuracy certificate, a moderately accurate bound, or a large-scale approximate solution.

Combinatorial optimization and approximation guarantees

Many discrete optimization problems can be expressed using rank-one positive semidefinite matrices. If si∈{−1,1}s_i\in\{-1,1\}, the matrix X=ssTX=ss^{\mathsf T} satisfies

X⪰0,Xii=1,rank⁡(X)=1.X\succeq0,\qquad X_{ii}=1,\qquad \operatorname{rank}(X)=1.

Conversely, these properties imply a representation by signs. Dropping the rank restriction leaves a convex SDP. This illustrates a general strategy for integer programming: lift products of variables into matrix entries and relax the nonconvex condition enforcing their common origin.

For the weighted maximum-cut problem, let wij≥0w_{ij}\geq0 be edge weights. A sign vector defines a cut with value

∑{i,j}∈Ewij1−sisj2.\sum_{\{i,j\}\in E}w_{ij}\frac{1-s_is_j}{2}.

Its semidefinite relaxation is

maximize⁡∑{i,j}∈Ewij1−Xij2subject to⁡Xii=1,X⪰0.\begin{aligned} \operatorname{maximize}\quad& \sum_{\{i,j\}\in E}w_{ij}\frac{1-X_{ij}}2\\ \operatorname{subject\ to}\quad& X_{ii}=1,\qquad X\succeq0. \end{aligned}

Every cut yields a feasible matrix, so the SDP optimum is an upper bound on the maximum cut value. Through a Gram representation, the relaxed variables become unit vectors viv_i with Xij=viTvjX_{ij}=v_i^{\mathsf T}v_j.

Goemans–Williamson rounding chooses a random hyperplane through the origin and assigns vertices according to the side containing each viv_i. If two vectors make angle θ\theta, the probability that they are separated is θ/π\theta/\pi, whereas the corresponding relaxed edge contribution is (1−cos⁡θ)/2(1-\cos\theta)/2. Comparing these expressions gives the expected approximation ratio

αGW=min⁡0<θ≤π2θπ(1−cos⁡θ)≈0.87856.\alpha_{\mathrm{GW}} =\min_{0<\theta\leq\pi} \frac{2\theta}{\pi(1-\cos\theta)} \approx0.87856.

Thus the rounded cut has expected weight at least this fraction of the optimum. The guarantee follows from a geometric probability calculation, not simply from the SDP being a close numerical bound.

The Lovász theta function provides another fundamental example. For a graph GG, one formulation is

ϑ(G)=max⁡{⟨J,X⟩:tr⁡(X)=1,  Xij=0 for {i,j}∈E(G),  X⪰0},\vartheta(G)= \max\left\{ \langle J,X\rangle: \operatorname{tr}(X)=1,\; X_{ij}=0\text{ for }\{i,j\}\in E(G),\; X\succeq0 \right\},

where JJ is the all-ones matrix. It satisfies

α(G)≤ϑ(G)≤χ(G‾),\alpha(G)\leq\vartheta(G)\leq\chi(\overline G),

linking the independence number and the chromatic number of the complement. For the five-cycle, ϑ(C5)=5\vartheta(C_5)=\sqrt5.

Relaxation quality varies substantially by problem. Some formulations are exact on special graph classes; others have large integrality gaps, meaning that their optimal values remain far from the best discrete solutions. Stronger semidefinite hierarchies add consistency constraints involving more variables, but increase problem size. In branch-and-bound algorithms, SDP bounds can help prune subproblems, while dual feasible solutions certify bounds independently of any rounding procedure.

Polynomial optimization and sums of squares

Semidefinite programming connects global polynomial optimization to algebraic certificates. A polynomial p(x)p(x) is a sum of squares if

p(x)=∑k=1rqk(x)2p(x)=\sum_{k=1}^r q_k(x)^2

for real polynomials qkq_k. Every sum of squares is globally nonnegative. For a polynomial of degree at most 2d2d, let zd(x)z_d(x) contain all monomials of total degree at most dd. Then

p(x) is a sum of squares⟺p(x)=zd(x)TQzd(x) for some Q⪰0.p(x)\text{ is a sum of squares} \quad\Longleftrightarrow\quad p(x)=z_d(x)^{\mathsf T}Qz_d(x) \text{ for some }Q\succeq0.

Matching coefficients gives linear equations in QQ, so testing for a sum-of-squares representation is an SDP.

Nonnegativity and being a sum of polynomial squares are not equivalent in general. David Hilbert’s 1888 classification identified special homogeneous cases where they coincide: quadratic forms, binary forms, and ternary quartic forms. A standard counterexample outside these cases is the Motzkin polynomial

x4y2+x2y4+1−3x2y2,x^4y^2+x^2y^4+1-3x^2y^2,

which is nonnegative but is not a sum of squares of real polynomials. Consequently, failure of a fixed-degree sum-of-squares test does not establish that a polynomial takes negative values.

For optimization over

K={x:gj(x)≥0, j=1,…,s},K=\{x:g_j(x)\geq0,\ j=1,\ldots,s\},

a lower bound γ\gamma for the minimum of ff can be certified by an identity

f−γ=σ0+∑j=1sσjgj,f-\gamma=\sigma_0+\sum_{j=1}^s\sigma_jg_j,

where the σj\sigma_j are sums of squares. Bounding their degrees produces an SDP. Increasing the degree gives a hierarchy of potentially stronger bounds. Under an Archimedean condition on the associated quadratic module, strict positivity on KK admits such certificates, yielding asymptotic convergence of the hierarchy. Compactness alone does not automatically make a chosen constraint representation Archimedean, although a suitable redundant ball constraint can supply this property for bounded sets.

The dual viewpoint uses truncated moment sequences. A moment sequence yαy_\alpha formally represents integrals of monomials xαx^\alpha. The moment matrix has entries

Md(y)α,β=yα+β.M_d(y)_{\alpha,\beta}=y_{\alpha+\beta}.

If these numbers arise from a nonnegative measure, then Md(y)⪰0M_d(y)\succeq0, because integrating any squared polynomial gives a nonnegative result. Localizing matrices encode the support conditions gj≥0g_j\geq0. Certain rank or flatness conditions allow finitely supported measures, and hence candidate global minimizers, to be extracted.

Jean Lasserre’s moment hierarchy and Pablo Parrilo’s semidefinite approach to sum-of-squares certificates, developed around 2000–2001, made this connection a practical computational framework. Its main limitation is combinatorial growth: zdz_d contains (n+dd)\binom{n+d}{d} monomials in nn variables. Symmetry, sparsity, and adapted polynomial bases can greatly reduce particular instances, but do not remove the general difficulty of global polynomial optimization.

Applications in control, statistics, and quantum information

In control theory, semidefinite programming turns many stability and performance conditions into computationally testable matrix inequalities. For the continuous-time linear system

x˙=Ax,\dot x=Ax,

the matrix AA is Hurwitz—every eigenvalue has negative real part—if and only if there exists P≻0P\succ0 such that

ATP+PA≺0.A^{\mathsf T}P+PA\prec0.

The function V(x)=xTPxV(x)=x^{\mathsf T}Px then decreases along every nonzero trajectory. This is the quadratic Lyapunov stability certificate underlying numerous control applications.

Strict inequalities are normally implemented with margins, for example

P⪰I,ATP+PA⪯−I,P\succeq I,\qquad A^{\mathsf T}P+PA\preceq-I,

when homogeneity permits scaling to that form. For uncertain dynamics described by a convex hull of finitely many system matrices, one common PP satisfying the inequalities at all vertices certifies stability throughout the hull. Such a common quadratic certificate is sufficient but may be conservative. Controller synthesis is more delicate: products involving an unknown controller and an unknown Lyapunov matrix can create bilinear matrix inequalities, which are not SDPs unless a valid reformulation removes the bilinearity.

In statistics, positive semidefiniteness expresses the basic consistency of a covariance matrix. Estimating a covariance matrix from incomplete or noisy pairwise information can therefore involve optimization over the semidefinite cone. The nearest correlation-matrix problem additionally imposes unit diagonal. A Frobenius-norm fitting objective is convex but not linear in the matrix entries; it can be transformed into conic epigraph form when a strict SDP representation is desired. Not every convex covariance-estimation problem is an SDP: for example, objectives involving a log determinant naturally lead to a broader class of convex matrix problems.

Semidefinite constraints also arise in low-rank recovery. For a rectangular matrix MM, its nuclear norm, the sum of its singular values, has the representation

∥M∥∗=min⁡U,V{tr⁡(U)+tr⁡(V)2:(UMMTV)⪰0}.\|M\|_*= \min_{U,V} \left\{ \frac{\operatorname{tr}(U)+\operatorname{tr}(V)}2: \begin{pmatrix}U&M\\M^{\mathsf T}&V\end{pmatrix}\succeq0 \right\}.

This makes nuclear-norm minimization an SDP and connects matrix completion with convex surrogates for rank. Applications range from recovering partially observed matrices to identifying low-dimensional structure, though large-scale implementations often exploit specialized algorithms rather than a generic SDP solver.

In quantum mechanics, density matrices are complex Hermitian positive semidefinite matrices with trace one. Measurement probabilities are linear functions of these matrices, making SDP a natural language for optimization over states and measurements. For binary state discrimination with prior probabilities p0,p1p_0,p_1 and density matrices ρ0,ρ1\rho_0,\rho_1, the optimal success probability is obtained from

max⁡0⪯E⪯I[p0tr⁡(Eρ0)+p1tr⁡((I−E)ρ1)].\max_{0\preceq E\preceq I} \left[ p_0\operatorname{tr}(E\rho_0) +p_1\operatorname{tr}((I-E)\rho_1) \right].

Here EE describes one outcome of a two-outcome measurement. More advanced applications use semidefinite relaxations to bound entanglement-related quantities and quantum correlations. The physical state constraints are naturally semidefinite, but additional requirements such as exact separability need not have a simple finite SDP description.