×

Further relaxations of the semidefinite programming approach to sensor network localization. (English) Zbl 1173.90498

Summary: Recently, a semidefinite programming (SDP) relaxation approach has been proposed to solve the sensor network localization problem. Although it achieves high accuracy in estimating the sensor locations, the speed of the SDP approach is not satisfactory for practical applications. In this paper we propose methods to further relax the SDP relaxation, more precisely, to relax the single semidefinite matrix cone into a set of small-size semidefinite submatrix cones, which we call a sub-SDP (SSDP) approach. We present two such relaxations. Although they are weaker than the original SDP relaxation, they retain the key theoretical property, and numerical experiments show that they are both efficient and accurate. The speed of the SSDP is even faster than that of other approaches based on weaker relaxations. The SSDP approach may also pave a way to efficiently solving general SDP problems without sacrificing the solution quality.

MSC:

90C22 Semidefinite programming
49M20 Numerical methods of relaxation type
65K05 Numerical mathematical programming methods

Software:

SeDuMi; COL; SNLSDP
PDFBibTeX XMLCite
Full Text: DOI Link