Optimization Online


Exploiting Sparsity in SDP Relaxation for Sensor Network Localization

Sunyoung Kim(skim***at***ewha.ac.kr)
Masakazu Kojima(kojima***at***is.titech.ac.jp)
Hayato Waki(waki9***at***is.titech.ac.jp)

Abstract: A sensor network localization problem can be formulated as a quadratic optimization problem (QOP). For quadratic optimization problems, semidefinite programming (SDP) relaxation by Lasserre with relaxation order 1 for general polynomial optimization problems (POPs) is known to be equivalent to the sparse SDP relaxation by Waki {¥it et al.} with relaxation order 1, except the size and sparsity of the resulting SDP relaxation problems. We show that the sparse SDP relaxation applied to the QOP is at least as strong as the Biswas-Ye SDP relaxation for the sensor network localization problem. A sparse variant of the Biswas-Ye SDP relaxation, which is equivalent to the original Biswas-Ye SDP relaxation, is also derived. Numerical results are compared with the Biswas-Ye SDP relaxation and the edge-based SDP relaxation by Wang {¥it et al.}. We show that the proposed sparse SDP relaxation is faster than the Biswas-Ye SDP relaxation. In fact, the computational efficiency in solving the resulting SDP problems increases as the number of anchors and/or the radio range grow. The proposed sparse SDP relaxation also provides more accurate solutions than the edge-based SDP relaxation when exact distances are given between sensors and anchors and there are only a small number of anchors.

Keywords: Sensor network localization problem, polynomial optimization problem, semidefinite relaxation, sparsity

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Research report B-447, Tokyo Institute of Technology, January, 2008

Download: [PDF]

Entry Submitted: 01/15/2008
Entry Accepted: 01/15/2008
Entry Last Modified: 01/15/2008

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society