SDP Relaxation

Semidefinite Programming (SDP) Relaxation is the technique of replacing a hard combinatorial optimization problem with a convex optimization problem over the cone of positive semidefinite matrices. The relaxation is constructed by lifting the original variables into a higher-dimensional matrix space, where nonlinear constraints become linear and the problem becomes tractable. SDP relaxations are the core algorithmic tool behind the sum-of-squares hierarchy and provide the best-known polynomial-time approximations for problems ranging from MAX-CUT to sparse PCA. The quality of an SDP relaxation is measured by its integrality gap — the ratio between the relaxed optimum and the true optimum — which can remain large even for sophisticated relaxations.

The power of SDP relaxation is also its limitation: by making the problem convex, it destroys the very combinatorial structure that made the problem interesting. The integrality gap is not an engineering failure but a mathematical signal that the problem's true complexity lives in the non-convex regime.