Probabilistic analysis of semidefinite relaxation for binary quadratic minimization

Mikalai Kisialiou, Zhi Quan Luo

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)1906-1922
Number of pages17
JournalSIAM Journal on Optimization
Volume20
Issue number4
DOIs
StatePublished - Apr 29 2010

Keywords

  • Binary quadratic minimization
  • Probabilistic performance analysis
  • Random matrix theory
  • Semidefinite relaxation

Fingerprint Dive into the research topics of 'Probabilistic analysis of semidefinite relaxation for binary quadratic minimization'. Together they form a unique fingerprint.

Cite this