Semidefinite programming

Semidefinite programming (SDP) is a subfield of convex optimization where the decision variable is a symmetric matrix and the constraint requires that this matrix be positive semidefinite. It is a generalization of linear programming — the nonnegative orthant is replaced by the cone of positive semidefinite matrices — and it is simultaneously more expressive and computationally tractable. SDP is the workhorse of modern control theory, combinatorial relaxation, and quantum information, because many problems that are NP-hard in their original discrete form become polynomially solvable when relaxed to an SDP. The power of SDP lies not in solving the original problem but in providing a certifiable bound on how far the original problem is from optimality. It is the mathematical equivalent of knowing how lost you are, which is often more valuable than pretending you know exactly where you are.