Semidefinite Programming

Semidefinite programming (SDP) is a powerful and elegant generalization of linear programming that has revolutionized optimization theory and its applications. While linear programming restricts you to linear constraints on a vector of variables, SDP allows you to optimize over the rich, non-polyhedral cone of positive semidefinite (PSD) matrices. This framework lets you model a vast array of non-linear and combinatorial problems as convex optimization problems, unlocking efficient solution methods and profound theoretical insights in fields from quantum physics to control systems.

From Linear to Semidefinite Cones

At its heart, a semidefinite program is an optimization problem where the variable is a symmetric matrix $X$ that is constrained to be positive semidefinite. Recall that a symmetric matrix $X\in {\mathbb{S}}^n$ is positive semidefinite (denoted $X⪰0$) if and only if all its eigenvalues are non-negative, or equivalently, $z^{T}Xz\ge 0$ for all vectors $z\in {\mathbb{R}}^n$.

The primal form of a standard SDP is: $$\begin{array}{rl}\text{minimize}& ⟨C,X⟩\\ \text{subject to}& ⟨A_i,X⟩=b_i,i=1,\dots ,m\\ & X⪰0\end{array}$$ Here, $C,A_i\in {\mathbb{S}}^n$ are given symmetric matrices, $b\in {\mathbb{R}}^m$ is a vector, and $⟨A,B⟩=\text{Tr}(A^{T}B)$ denotes the trace inner product. The objective is linear in the matrix variable $X$, and the constraints are linear equalities plus the crucial conic constraint $X⪰0$. This formulation directly extends linear programming: instead of a vector $x\ge 0$ (the non-negative orthant cone), the variable lies in the cone of PSD matrices.

The Power of Duality

A deep and practical feature of semidefinite programming is its associated duality theory. For every primal SDP, we can construct a dual problem. The Lagrange dual of the primal SDP presented above is: $$\begin{array}{rl}\text{maximize}& b^{T}y\\ \text{subject to}& C-\sum _{i=1}^m{y}_i{A}_i⪰0\end{array}$$ Here, $y\in {\mathbb{R}}^m$ is the dual variable. The constraint $S=C-{\sum }_i{y}_i{A}_i⪰0$ forces the dual slack matrix $S$ to be PSD. Weak duality always holds: for any feasible primal $X$ and dual $(y,S)$, we have $⟨C,X⟩\ge b^{T}y$. Under a standard constraint qualification (e.g., the existence of a strictly feasible point $X\succ 0$), strong duality holds, meaning the optimal primal and dual values coincide and both are attained. Duality is not just a theoretical tool; it provides a certificate of optimality and is fundamental to the most efficient solving algorithms.

Solving with Interior-Point Methods

The most successful algorithms for solving SDPs at scale are interior-point methods. These methods solve the primal and dual problems simultaneously by following a central path through the interior of the feasible region ($X\succ 0$, $S\succ 0$). The core idea is to replace the conic constraints with a logarithmic barrier function. For the PSD cone, the standard barrier is $-\log \det (X)$, which goes to infinity as $X$ approaches the boundary of the cone (i.e., as its smallest eigenvalue approaches zero).

The algorithm iteratively solves a series of linearized Newton systems derived from the perturbed Karush-Kuhn-Tucker (KKT) conditions: $$\begin{array}{rl}⟨A_i,X⟩& =b_i,\\ \sum _i{y}_i{A}_i+S& =C,\\ XS& =\mu I,\end{array}$$ where $\mu >0$ is a barrier parameter that is gradually reduced to zero. The last equation, $XS=\mu I$, is the relaxed complementarity slackness condition for cones. Solving the linear system for the Newton step is computationally intensive, as it typically involves $O(m^2{n}^2)$ operations, limiting the size of problems solvable by general-purpose interior-point codes. However, for many structured problems (e.g., those with sparse or low-rank data matrices), these costs can be drastically reduced.

Applications Across Disciplines

The true value of SDP lies in its remarkable modeling power. Its applications are a testament to the unity of mathematical ideas.

• Combinatorial Optimization: SDP provides the strongest known polynomial-time approximations for famous NP-hard problems. The seminal example is the Goemans-Williamson algorithm for the Maximum Cut problem. The problem is first relaxed into an SDP, whose solution is a set of high-dimensional vectors. A random hyperplane is then used to "round" these vectors back to a $\pm 1$ cut, yielding a provably high-quality approximate solution. Similar SDP relaxations are central to problems like graph coloring, sparsest cut, and community detection.
• Control Theory: Many problems in robust and optimal control can be formulated using Linear Matrix Inequalities (LMIs), which are special cases of SDP constraints. For instance, checking the stability of a linear system $\dot{x}=Ax$ reduces to finding a matrix $P\succ 0$ such that $A^{T}P+PA\prec 0$ (the Lyapunov inequality). More complex problems, like designing a controller that minimizes the worst-case effect of disturbances ($H_{\infty }$ control), are naturally framed and solved as SDPs.
• Quantum Information Theory: The SDP cone perfectly models the set of quantum states (density matrices), which are Hermitian, PSD matrices with trace one. Key tasks like computing the fidelity between two quantum states, determining the optimal probability of distinguishing states, or verifying entanglement can be cast as SDPs. This has made SDP an indispensable computational tool in quantum computing and quantum cryptography.

Common Pitfalls

1. Ignoring Constraint Qualifications: Assuming strong duality always holds can lead to incorrect conclusions or algorithm failure. Always verify (or ensure the existence of) a strictly interior point (e.g., an $X\succ 0$ satisfying the linear constraints) for your specific problem before applying duality-based results or algorithms that rely on them.
2. Misinterpreting the Duality Gap: In practice, numerical solvers terminate with a small but non-zero duality gap. Treating this as exact optimality can be dangerous in sensitive applications. You should check the reported duality gap and primal/dual infeasibilities to assess solution quality.
3. Scalability Blindness: Formulating a problem as a general, dense SDP without considering structure is a recipe for computational intractability. Before coding, analyze your problem for sparsity, symmetry, or low-rank inherent in the data matrices $C$ and $A_i$. Exploiting this structure, often with specialized solvers, can mean the difference between solving a problem and hitting memory limits.
4. Over-Reliance on Off-the-Shelf Solvers: While powerful, generic SDP solvers may not be the most efficient tool for every problem. For instance, very large-scale problems might be better tackled with first-order methods (e.g., the Alternating Direction Method of Multipliers) that sacrifice some accuracy for the ability to handle millions of variables.

Summary

• Semidefinite programming extends linear optimization from the non-negative orthant to the cone of positive semidefinite matrices, enabling the modeling of a wide range of non-linear and combinatorial problems.
• Strong duality theory provides optimality certificates and is the foundation for efficient interior-point methods, which solve SDPs by navigating a central path defined by a logarithmic barrier function.
• SDPs have profound applications: they provide the best-known approximations for NP-hard combinatorial problems, formulate stability and control problems via linear matrix inequalities, and model fundamental tasks in quantum information theory.
• Successful use requires awareness of constraint qualifications for duality, careful assessment of numerical solution quality, and strategic exploitation of problem structure to manage computational complexity.