Optimization Online


Robust Semidefinite Programming Approaches for Sensor Network Localization with Anchors

Nathan Krislock (ngbkrislock***at***uwaterloo.ca)
Veronica Piccialli (Veronica.Piccialli***at***dis.uniroma1.it)
Henry Wolkowicz (hwolkowicz***at***uwaterloo.ca)

Abstract: We derive a robust primal-dual interior-point algorithm for a semidefinite programming, SDP, relaxation for sensor localization with anchors and with noisy distance information. The relaxation is based on finding a Euclidean Distance Matrix, EDM, that is nearest in the Frobenius norm for the known noisy distances and that satisfies given upper and lower bounds on the unknown distances. We show that the SDP relaxation for this nearest EDM problem is usually underdetermined and is an ill-posed problem. Our interior-point algorithm exploits the structure and maintains exact feasibility at each iteration. High accuracy solutions can be obtained despite the ill-conditioning of the optimality conditions. Included are discussions on the strength and stability of the SDP relaxations, as well as results on invariant cones related to the operators that map between the cones of semidefinite and Euclidean distance matrices.

Keywords: Sensor Network Localization, Anchors, Graph Realization, Semidefinite Programming, Euclidean Distance Matrix Completions, Gauss-Newton Method

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Applications -- OR and Management Sciences

Category 3: Applications -- Science and Engineering (Civil and Environmental Engineering )

Citation: Research Report CORR 12, Dept. Combinatorics and Optimization, University of Waterloo, May/06

Download: [PDF]

Entry Submitted: 05/21/2006
Entry Accepted: 05/21/2006
Entry Last Modified: 05/21/2006

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