Further relaxations of the semidefinite programming approach to sensor network localization

Zizhuo Wang, Song Zheng, Yinyu Ye, Stephen Boyd

Research output: Contribution to journalArticlepeer-review

125 Scopus citations

Abstract

Recently, a semidefinite programming (SDP) relaxation approach has been proposed to solve the sensor network localization problem. Although it achieves high accuracy in estimating the sensor locations, the speed of the SDP approach is not satisfactory for practical applications. In this paper we propose methods to further relax the SDP relaxation, more precisely, to relax the single semidefinite matrix cone into a set of small-size semidefinite submatrix cones, which we call a sub-SDP (SSDP) approach. We present two such relaxations. Although they are weaker than the original SDP relaxation, they retain the key theoretical property, and numerical experiments show that they are both efficient and accurate. The speed of the SSDP is even faster than that of other approaches based on weaker relaxations. The SSDP approach may also pave a way to efficiently solving general SDP problems without sacrificing the solution quality.

Original languageEnglish (US)
Pages (from-to)655-673
Number of pages19
JournalSIAM Journal on Optimization
Volume19
Issue number2
DOIs
StatePublished - Jun 1 2008

Keywords

  • Chordal graph
  • Principal submatrix
  • Second-order cone programming
  • Semidefinite programming
  • Sensor network localization

Fingerprint Dive into the research topics of 'Further relaxations of the semidefinite programming approach to sensor network localization'. Together they form a unique fingerprint.

Cite this