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.