(Robust) edge-based semidefinite programming relaxation of sensor network localization

DOI10.1007/s10107-009-0338-xzbMath1231.90308OpenAlexW2069684697WikidataQ57511251 ScholiaQ57511251MaRDI QIDQ652286

Ting Kei Pong, Paul Tseng

Publication date: 14 December 2011

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-009-0338-x

zbMATH Keywords

semidefinite programmingsemidefinite programming relaxationsensor network localizationcoordinate gradient descentlog-barrier penalty method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Large-scale problems in mathematical programming (90C06) Applications of mathematical programming (90C90) Sensitivity, stability, parametric optimization (90C31) Numerical methods of relaxation type (49M20) Distributed algorithms (68W15)

Related Items

A penalty method for rank minimization problems in symmetric matrices, Approximation accuracy, gradient methods, and error bound for structured convex optimization, Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier, A DC programming approach for sensor network localization with uncertainties in anchor positions, Geometric buildup algorithms for sensor network localization, Visualizing data as objects by DC (difference of convex) optimization, Comparing SOS and SDP relaxations of sensor network localization, Edge-based semidefinite programming relaxation of sensor network localization with lower bound constraints, On bar frameworks, stress matrices and semidefinite programming, Euclidean Distance Matrices and Applications, A modified quasisecant method for global optimization, Selected Open Problems in Discrete Geometry and Optimization

Uses Software

• SeDuMi
• SFSDP
• SNLSDP

Cites Work

• Unnamed Item
• Sensor network localization, Euclidean distance matrix completions, and graph realization
• Sum of squares method for sensor network localization
• Theory of semidefinite programming for sensor network localization
• A coordinate gradient descent method for nonsmooth separable minimization
• Graph rigidity via Euclidean distance matrices
• Asymptotic behavior of the central path for a special class of degenerate SDP problems
• Further Relaxations of the Semidefinite Programming Approach to Sensor Network Localization
• A Distributed SDP Approach for Large-Scale Noisy Anchor-Free Graph Realization with Applications to Molecular Conformation
• Global Continuation for Distance Geometry Problems
• Exploiting Sparsity in SDP Relaxation for Sensor Network Localization
• Algorithmic Aspects of Wireless Sensor Networks
• SpaseLoc: An Adaptive Subproblem Algorithm for Scalable Wireless Sensor Network Localization
• Second‐Order Cone Programming Relaxation of Sensor Network Localization