Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1137/080713380 | SIAM Journal on Optimization |
Keywords | Field | DocType |
polynomial optimization probl em,biswas-ye sdp relaxation,sdp relaxation,sensor network localization problem,relaxation order,general polynomial optimization problem,sparsity.,sparse variant,edge-based sdp relaxation,original biswas-ye sdp relaxation,sensor network localization,semidefi- nite relaxation,sparse sdp relaxation,exploiting sparsity,sdp relaxation problem,quadratic optimization,sparsity,sensor network | Polynomial optimization,Discrete mathematics,Mathematical optimization,Quadratic programming,Wireless sensor network,Semidefinite programming,Mathematics | Journal |
Volume | Issue | ISSN |
20 | 1 | 1052-6234 |
Citations | PageRank | References |
39 | 1.36 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. Kim | 1 | 248 | 14.25 |
| Masakazu Kojima | 2 | 1603 | 222.51 |
| Hayato Waki | 3 | 376 | 28.82 |