Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
复制标题
DOI：
10.1137/080713380
复制
发表时间：
2009-03
期刊：
影响因子：
--
通讯作者：
Sunyoung Kim;M. Kojima;Hayato Waki
中科院分区：
文献类型：
--
作者：
Sunyoung Kim;M. Kojima;Hayato Waki
传感器网络定位问题可以归结为二次优化问题。对于QOPS，一般多项式优化问题(POPS)的Lasserre松弛阶为1的半定规划(SDP)松弛等价于Waki等人的稀疏SDP松弛。松弛阶为1，除了所产生的SDP松弛问题的大小和稀疏性之外。对于传感器网络局部化问题，我们证明了应用于QOP的稀疏SDP松弛至少与Biswas-Ye SDP松弛一样强。文中还给出了与原来的Biswas-Ye SDP松弛等价的Biswas-Ye SDP松弛的稀疏变形。我们在数值上比较了应用于QOP的稀疏SDP松弛、Biswas-Ye SDP松弛及其稀疏变种以及Wang等人提出的基于边的SDP松弛。为了验证所提出的利用SDP松弛中的稀疏性来解决传感器网络定位问题的有效性。应用于QOP的稀疏SDP松弛比Biswas-Ye SDP松弛快得多，并且Biswas-Ye SDP松弛的稀疏变体在速度上优于所有其他SDP松弛。
A sensor network localization problem can be formulated as a quadratic optimization problem (QOP). For QOPs, 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 et al. with relaxation order 1, except for 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. We compare numerically the sparse SDP relaxation applied to the QOP, the Biswas-Ye SDP relaxation, its sparse variant, and the edge-based SDP relaxation by Wang et al. to confirm the effectiveness of the proposed techniques for exploiting the sparsity in SDP relaxation for sensor network localization problems. The sparse SDP relaxation applied to the QOP is much faster than the Biswas-Ye SDP relaxation, and the sparse variant of the Biswas-Ye SDP relaxation outperforms all other SDP relaxations in speed.