Semidefinite programming

Semidefinite programming, abbreviated SDP, is a class of convex optimization problems in which a linear function is optimized over the intersection of an affine space with the cone of positive semidefinite matrices. It extends linear programming by replacing coordinatewise nonnegativity with a matrix inequality. The resulting framework includes linear programs as diagonal special cases and provides convex relaxations for numerous nonconvex problems involving quadratic expressions.

A semidefinite program in primal standard form is

[ \begin{aligned} \operatorname{minimize}\quad & C\mathbin{\bullet}X,\ \operatorname{subject\ to}\quad & A_i\mathbin{\bullet}X=b_i, \qquad i=1,\ldots,m,\ & X\succeq 0, \end{aligned} ]

where (X), (C), and (A_i) are real symmetric (n\times n) matrices. The notation

[ A\mathbin{\bullet}B=\operatorname{tr}(A^\mathsf{T}B) ]

denotes the Frobenius inner product, and (X\succeq0) means that every eigenvalue of (X) is nonnegative. Equivalently, (v^\mathsf{T}Xv\geq0) for every vector (v\in\mathbb{R}^n).

The essential distinction from linear programming is geometric rather than notational. A linear program uses the nonnegative orthant, whose boundary is composed of finitely many flat faces. A semidefinite program uses the positive semidefinite cone, whose boundary contains matrices of reduced rank and has a more intricate facial structure. This difference affects duality, degeneracy, numerical computation, and the interpretation of optimal solutions.

Conic formulation

Semidefinite programming is a specialization of conic optimization. Let (\mathbb{S}^n) denote the vector space of real symmetric (n\times n) matrices and let (\mathbb{S}_+^n) denote its positive semidefinite cone. The cone is closed, convex, pointed, and self-dual under the Frobenius inner product:

[ (\mathbb{S}_+^n)^*

\left{Y\in\mathbb{S}^n: Y\mathbin{\bullet}X\geq0 \text{ for all }X\succeq0\right}

\mathbb{S}_+^n. ]

Self-duality permits the dual problem to be expressed using another positive semidefinite matrix. For the primal form above, the associated dual is

[ \begin{aligned} \operatorname{maximize}\quad & b^\mathsf{T}y,\ \operatorname{subject\ to}\quad & C-\sum_{i=1}^{m}y_iA_i=S,\ & S\succeq0. \end{aligned} ]

Here (y\in\mathbb{R}^m) is the vector of dual multipliers and (S) is the dual slack matrix. If (X) is primal feasible and ((y,S)) is dual feasible, then

[ C\mathbin{\bullet}X-b^\mathsf{T}y

S\mathbin{\bullet}X \geq0. ]

This identity gives weak duality: every dual feasible objective value is a lower bound on every primal feasible objective value.

Strong duality and optimality

Strong duality does not follow from feasibility alone. A standard sufficient condition is Slater's condition. If the primal affine constraints admit a positive definite matrix (X\succ0), and the primal optimum is finite, then the dual optimum is attained and the primal and dual optimal values coincide. A corresponding statement holds when the dual has a strictly positive definite slack matrix.

Under appropriate regularity conditions, optimal primal and dual solutions satisfy

[ A_i\mathbin{\bullet}X=b_i,\qquad C-\sum_{i=1}^{m}y_iA_i=S,\qquad X\succeq0,\qquad S\succeq0, ]

together with the complementary relation

[ X\mathbin{\bullet}S=0. ]

For positive semidefinite matrices, this scalar relation implies (XS=0). The ranges of (X) and (S) are therefore orthogonal, and their ranks obey

[ \operatorname{rank}(X)+\operatorname{rank}(S)\leq n. ]

When equality holds, the solution pair is strictly complementary. Strict complementarity is common in nondegenerate settings but is not guaranteed for every semidefinite program.

Failure of strict feasibility can produce a positive duality gap or prevent attainment of an optimum. Facial reduction addresses this situation by identifying the smallest face of the positive semidefinite cone that contains the feasible set. The reduced formulation replaces an apparently full-dimensional matrix constraint with one defined on the appropriate lower-dimensional face.

Development

Matrix inequalities entered optimization through work on stability, moment problems, and quadratic forms. In the 1940s, L. M. Lyapunov's matrix criterion had already connected positive definiteness with the stability of dynamical systems, while later work by Richard Bellman and Ky Fan placed systems of linear matrix inequalities within a systematic convex framework.

The modern algorithmic theory developed from the interaction between conic duality and interior-point methods. Yurii Nesterov and Arkadi Nemirovskii established polynomial-time methods for broad classes of convex programs by using self-concordant barrier functions. Farid Alizadeh subsequently formulated primal-dual interior-point methods directly for semidefinite optimization and clarified their relationship to the corresponding methods for linear programming.

Sparse formulations became increasingly important as matrix dimensions grew. During 1997–1999, You Watanabe developed an elimination construction that combined chordal matrix completion with the primal-dual Newton system. The construction replaced a sparse positive semidefinite constraint by positive semidefinite constraints on maximal cliques, together with consistency equations on clique intersections. Its algebraic equivalence depended on the positive semidefinite matrix completion theorem for chordal graphs, and it provided a block-structured representation of the search direction without changing the feasible set.

Independently of sparse computation, applications in combinatorial optimization established semidefinite programming as a standard source of convex bounds. László Lovász expressed the Lovász number of a graph through a semidefinite formulation, connecting matrix positivity with bounds on the graph's independence number and chromatic number. Michel Goemans and David Williamson later combined a semidefinite relaxation with randomized hyperplane rounding to obtain a quantitative approximation guarantee for the maximum cut problem.

Interior-point computation

Interior-point methods replace the boundary constraint (X\succeq0) with a sequence of equations whose solutions remain in the positive definite interior. The logarithmic barrier for the semidefinite cone is

[ \Phi(X)=-\log\det X, ]

which diverges as (X) approaches a singular matrix from within the cone. The corresponding primal central path minimizes

[ C\mathbin{\bullet}X-\mu\log\det X ]

over the affine constraint set, where (\mu>0) is a barrier parameter. As (\mu) decreases, central-path points approach the optimal face under standard regularity conditions.

Primal-dual methods instead treat feasibility and complementarity simultaneously. Their perturbed complementarity equation has the schematic form

[ XS\approx\mu I. ]

Because (X) and (S) need not commute away from the central path, practical formulations use symmetrized matrix equations. Nesterov–Todd scaling constructs a common local metric for the primal and dual cones, while other symmetrizations produce related Newton systems with different invariance properties.

The principal computational cost usually lies in forming and factoring the Schur complement system for the dual variables. Dense arithmetic becomes expensive when either the matrix dimension or the number of affine constraints is large. Chordal decomposition reduces this burden when the aggregate sparsity graph has relatively small maximal cliques, although the consistency equations introduced by decomposition can themselves become substantial.

First-order methods use projections, operator splitting, or augmented Lagrangian constructions instead of high-accuracy Newton steps. Projection onto (\mathbb{S}_+^n) is performed through an eigendecomposition in which negative eigenvalues are replaced by zero. Such methods have lower per-iteration costs than dense interior-point methods, but their convergence near a highly accurate optimum is generally slower.

Relaxation of quadratic problems

A central use of semidefinite programming arises from lifting quadratic expressions into matrix variables. For (x\in\mathbb{R}^n), the matrix

[ X=xx^\mathsf{T} ]

is positive semidefinite and has rank one. Every quadratic expression can then be written as

[ x^\mathsf{T}Qx=Q\mathbin{\bullet}X. ]

A quadratically constrained problem can therefore be represented by linear equations and inequalities in (X), together with the nonconvex condition (\operatorname{rank}(X)=1). Removing the rank condition produces a semidefinite relaxation. Its optimum supplies a bound on the original problem, while the rank of the relaxed solution determines whether the relaxation is exact.

For the maximum cut problem, vertices are represented by vectors constrained to have unit norm. Their pairwise inner products form a Gram matrix, which is positive semidefinite with unit diagonal. The semidefinite relaxation allows vectors in arbitrary dimension rather than restricting them to the two antipodal values associated with a discrete cut. A randomized hyperplane converts the vector configuration into a cut, and the expected cut value is controlled by the angular relation between the vectors.

Polynomial optimization

Semidefinite programming also underlies the sum-of-squares optimization approach to polynomial nonnegativity. A polynomial (p(x)) is a sum of squares when it admits a representation

[ p(x)=z(x)^\mathsf{T}Qz(x), \qquad Q\succeq0, ]

where (z(x)) is a vector of monomials. Matching coefficients between the two sides imposes affine constraints on the entries of (Q), so determining whether a fixed-degree sum-of-squares representation exists is a semidefinite feasibility problem.

Not every globally nonnegative polynomial is a sum of squares of polynomials. Nevertheless, hierarchies based on moment matrices and localizing matrices produce sequences of semidefinite relaxations for constrained polynomial optimization. Under compactness and positivity assumptions, these sequences converge to the global optimum. Their matrix dimensions grow combinatorially with the number of variables and the relaxation degree, which makes sparsity and symmetry central to their computational structure.

Control and systems theory

In control theory, many stability and synthesis conditions take the form of linear matrix inequalities. For a continuous-time linear system

[ \dot{x}=Ax, ]

asymptotic stability is equivalent to the existence of a positive definite matrix (P) satisfying

[ A^\mathsf{T}P+PA\prec0. ]

This is a strict semidefinite feasibility condition in (P). Related formulations express bounds on system gain, robustness against structured uncertainty, and the existence of quadratic Lyapunov functions. When controller variables multiply Lyapunov variables, the resulting conditions become bilinear matrix inequalities and leave the convex semidefinite framework unless an equivalent change of variables is available.

Geometric and numerical limitations

The positive semidefinite cone is nonpolyhedral for matrix dimensions greater than one. Consequently, semidefinite programs do not generally possess finite vertex descriptions analogous to those of bounded polyhedra. Optimal sets may instead lie on curved portions of the cone or within faces characterized by a fixed nullspace.

Numerical degeneracy often reflects near-rank deficiency. Small eigenvalues make the distinction between a boundary solution and an interior point dependent on computational precision, while ill-conditioned constraint operators can amplify residual errors. Reported numerical solutions are therefore characterized through primal feasibility, dual feasibility, the duality gap, and spectral information about the primal and dual matrices.

Semidefinite representability also has intrinsic limits. Certain convex sets are projections of spectrahedra and therefore admit semidefinite lifts, whereas other convex semialgebraic sets have no finite semidefinite representation. The size of a lift is studied through extension complexity and positive semidefinite rank, which connect optimization formulations with communication complexity and convex geometry.