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.
Citation
Research Report CORR 12, Dept. Combinatorics and Optimization, University of Waterloo, May/06