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)


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
Issue number3
Publication statusPublished - 1 Jul 2012
Externally publishedYes


  • 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