Abstract
We investigate the relationships between various sum of squares (SOS) and semidefinite programming (SDP) relaxations for the sensor network localization problem. In particular, we show that Biswas and Ye’s SDP relaxation is equivalent to the degree one SOS relaxation of Kim et al. We also show that Nie’s sparse-SOS relaxation is stronger than the edge-based semidefinite programming (ESDP) relaxation, and that the trace test for accuracy, which is very useful for SDP and ESDP relaxations, can be extended to the sparse-SOS relaxation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alfakih, A., Anjos, M.F., Piccialli, V., Wolkowicz, H.: Euclidean distance matrices, semidefinite programming, and sensor network localization. Port. Math. 68(1), 53–102 (2011)
Alfakih, A., Khandani, A., Wolkowicz, H.: Solving Euclidean distance matrix completion problems via semidefinite programming. Comput. Optim. Appl. 12, 13–30 (1999)
Biswas, P., Ye, Y.: Semidefinite programming for ad hoc wireless sensor network localization. In: Proc. 3rd IPSN, Berkeley, CA, pp. 46–54 (2004)
Biswas, P., Ye, Y.: A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization. In: Mutiscale Optimization Methods and Applications, Nonconvex Optim. Appl., vol. 82, pp. 69–84. Springer, New York (2006)
Carter, W., Jin, H.H., Saunders, M.A., Ye, Y.: SpaseLoc: an adaptive subproblem algorithm for scalable wireless sensor network localization. SIAM J. Optim. 17, 1102–1128 (2006)
Ding, Y., Krislock, N., Qian, J., Wolkowicz, H.: Sensor network localization, Euclidean distance matrix completions, and graph realization. Optim. Eng. 11, 45–66 (2010)
Doherty, L., Pister, K.S.J., El Ghaoui, L.: Convex position estimation in wireless sensor networks. In: Proc. 20th INFOCOM, Los Alamitos, CA, vol. 3, pp. 1655–1663 (2001)
Kim, S., Kojima, M., Waki, H.: Exploiting sparsity in SDP relaxation for sensor network localization. SIAM J. Optim. 17, 192–215 (2009)
Krislock, N., Piccialli, V., Wolkowicz, H.: Robust semidefinite programming approaches for sensor network localization with anchors. Report, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, May 2006
Krislock, N., Rendl, F., Wolkowiz, H.: Noisy sensor network localization using semidefinite representations and facial reduction. Report, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, March 2010
Krislock, N., Wolkowicz, H.: Explicit sensor network localization using semidefinite representations and facial reductions. SIAM J. Optim. 20, 2679–2708 (2010)
Krislock, N., Wolkowicz, H.: Euclidean distance matrices and applications. In: Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications
Nie, J.: Sum of squares method for sensor network localization. Comput. Optim. Appl. 43, 151–179 (2009)
Nie, J., Demmel, J.: Sparse SOS relaxations for minimizing functions that are summations of small polynomials. SIAM J. Optim. 19, 1534–1558 (2008)
Pong, T.K., Tseng, P.: (Robust) edge-based semidefinite programming relaxation of sensor network localization. Math. Program. (2010). doi:10.1007/s10107-009-0338-x
So, A.M.-C., Ye, Y.: Theory of semidefinite programming for sensor network localization. Math. Program. 109, 367–384 (2007)
Sturm, J.F.: Using Se.Du.Mi. 1.02, A Matlab∗ toolbox for optimization over symmetric cones (updated for Version 1.05). Report, Department of Econometrics, Tilburg University, Tilburg, August 1998–October 2001
Tseng, P.: Second-order cone programming relaxation of sensor network localizations. SIAM J. Optim. 18, 156–185 (2007)
Wang, Z., Zheng, S., Ye, Y., Boyd, S.: Further relaxations of the semidefinite programming approach to sensor network localization. SIAM J. Optim. 19, 655–673 (2008)
Zhu, Z., So, A.M.-C., Ye, Y.: Universal rigidity and edge sparsification for sensor network localization. SIAM J. Optim. 20, 3059–3081 (2010)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gouveia, J., Pong, T.K. Comparing SOS and SDP relaxations of sensor network localization. Comput Optim Appl 52, 609–627 (2012). https://doi.org/10.1007/s10589-011-9431-1
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-011-9431-1