Probabilistic Analysis of Semidefinite Relaxation for Binary Quadratic Minimization

We consider semidefinite programming relaxation (SDR) of a binary quadratic minimization problem. This NP-hard problem arises naturally in the maximum-likelihood detection of discrete signals for digital communications. We analyze the average performance of the SDR algorithm for a class of randomly generated binary quadratic minimization problems. Although the SDR worst-case approximation ratio is unbounded for this NP-hard problem, our analysis shows that SDR can provide in polynomial time a provably near-optimal solution, achieving a constant factor approximation of the optimal objective value in probability. Moreover, this constant factor remains bounded with increasing problem size. Our proof is based on an asymptotic analysis of Karush–Kuhn–Tucker optimality conditions using random matrix theory.