Edge-based semidefinite programming relaxation of sensor network localization with lower bound constraints

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

In this paper, we strengthen the edge-based semidefinite programming relaxation (ESDP) recently proposed by Wang, Zheng, Boyd, and Ye (SIAM J. Optim. 19:655-673, 2008) by adding lower bound constraints. We show that, when distances are exact, zero individual trace is necessary and sufficient for a sensor to be correctly positioned by an interior solution. To extend this characterization of accurately positioned sensors to the noisy case, we propose a noise-aware version of ESDPlb(ρ-ESDPlb) and show that, for small noise, a small individual trace is equivalent to the sensor being accurately positioned by a certain analytic center solution. We then propose a postprocessing heuristic based on ρ-ESDPlband a distributed algorithm to solve it. Our computational results show that, when applied to a solution obtained by solving ρ-ESDP proposed of Pong and Tseng (Math. Program. doi: 10.1007/s10107-009-0338-x ), this heuristics usually improves the RMSD by at least 10%. Furthermore, it provides a certificate for identifying accurately positioned sensors in the refined solution, which is not common for existing refinement heuristics.
Original languageEnglish
Pages (from-to)23-44
Number of pages22
JournalComputational Optimization and Applications
Volume53
Issue number1
DOIs
Publication statusPublished - 1 Sep 2012
Externally publishedYes

Keywords

  • Coordinate gradient descent
  • Error bound
  • Log-barrier
  • Semidefinite programming relaxation
  • Sensor network localization

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Cite this