Comparing SOS and SDP relaxations of sensor network localization

João Gouveia, Ting Kei Pong

Research output: Journal article publicationJournal articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

We investigate the relationships between various sum of squares (SOS) and semidefinite programming (SDP) relaxations for the sensor network localization problem. In particular, we show that Biswas and Ye's SDP relaxation is equivalent to the degree one SOS relaxation of Kim et al. We also show that Nie's sparse-SOS relaxation is stronger than the edge-based semidefinite programming (ESDP) relaxation, and that the trace test for accuracy, which is very useful for SDP and ESDP relaxations, can be extended to the sparse-SOS relaxation.
Original languageEnglish
Pages (from-to)609-627
Number of pages19
JournalComputational Optimization and Applications
Volume52
Issue number3
DOIs
Publication statusPublished - 1 Jul 2012
Externally publishedYes

Keywords

  • Individual trace
  • Semidefinite programming relaxation
  • Sensor network localization
  • Sum of squares relaxation

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics
  • Control and Optimization

Cite this