Theory and Computation of Semidefinite
Programming for Sensor Network Localization and Other Euclidean
Distance Geometry Problems
Yinyu Ye
Department of Management Science and Engineering and
Institute for Computational and Mathematical Engineering
Stanford University
Joint colloquium with Institute for
Computational and Mathematical Engineering
Thursday, October 7, 2004
4:15 - 5:15 PM
Building 200, Room 205
Abstract:
We describe a semidefinite programming (SDP) based model
and method for the position estimation problem in Euclidean distance
geometry such as wireless sensor network localization. The optimization
problem is set up so as to minimize the error in sensor positions to
fit incomplete and noisy distance measures. We develop an SDP
relaxation model and use the duality theory to derive necessary and
sufficient conditions for whether a network is "localizable" or not,
when the distance measures are accurate; and present a polynomial-time
algorithm to locate it if it is localizable. We also present
probabilistic analyses of the SDP solution when the distance measures
are noisy. In all cases, observable gauges are developed to certify the
quality of the position estimation of every sensor and to detect
possible erroneous sensors. Furthermore, we develop a gradient-based
local search method to round and improve the SDP solution.
Computational solvers will be demonstrated to show the effectiveness of
the method.
Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html