Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions

DOI10.1137/090759392zbMath1229.90250arXiv1002.0013OpenAlexW2111826413MaRDI QIDQ121877

Henry Wolkowicz, Nathan Krislock, Henry Wolkowicz, Nathan Krislock

Publication date: January 2010

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1002.0013

zbMATH Keywords

semidefinite programmingEuclidean distance matrix completionssensor network localizationloss of the Slater constraint qualification

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Semidefinite programming (90C22) Large-scale problems in mathematical programming (90C06) Nonconvex programming, global optimization (90C26)

Related Items (38)

Euclidean distance matrix completion problems ⋮ DOUGLAS–RACHFORD FEASIBILITY METHODS FOR MATRIX COMPLETION PROBLEMS ⋮ Convex Euclidean distance embedding for collaborative position localization with NLOS mitigation ⋮ A least-squares approach for discretizable distance geometry problems with inexact distances ⋮ An application-based characterization of dynamical distance geometry problems ⋮ The discretizable distance geometry problem ⋮ Strong duality and minimal representations for cone optimization ⋮ Recent advances on the interval distance geometry problem ⋮ Noisy Euclidean Distance Realization: Robust Facial Reduction and the Pareto Frontier ⋮ Constraint programming approaches for the discretizable molecular distance geometry problem ⋮ Rejoinder on: ``Distance geometry and data science ⋮ Distance Geometry on the Sphere ⋮ Perturbation analysis of the Euclidean distance matrix optimization problem and its numerical implications ⋮ A numerical-and-computational study on the impact of using quaternions in the branch-and-prune algorithm for exact discretizable distance geometry problems ⋮ Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming ⋮ A fresh variational-analysis look at the positive semidefinite matrices world ⋮ Geometric buildup algorithms for sensor network localization ⋮ Computing the nearest Euclidean distance matrix with low embedding dimensions ⋮ Robust principal component analysis using facial reduction ⋮ Level-set methods for convex optimization ⋮ On Farkas lemma and dimensional rigidity of bar frameworks ⋮ Preface: Special issue dedicated to distance geometry ⋮ Low-rank matrix completion using nuclear norm minimization and facial reduction ⋮ edmcr ⋮ Comparing SOS and SDP relaxations of sensor network localization ⋮ Edge-based semidefinite programming relaxation of sensor network localization with lower bound constraints ⋮ The discretizable molecular distance geometry problem ⋮ Preprocessing and Regularization for Degenerate Semidefinite Programs ⋮ Validating numerical semidefinite programming solvers for polynomial invariants ⋮ Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone ⋮ Euclidean Distance Matrices and Applications ⋮ A new algorithm for the \(^K\)DMDGP subclass of distance geometry problems with exact distances ⋮ Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs ⋮ Barvinok's naive algorithm in distance geometry ⋮ Euclidean Distance Matrix Completion and Point Configurations from the Minimal Spanning Tree ⋮ Diagonally Dominant Programming in Distance Geometry ⋮ Coordinate Shadows of Semidefinite and Euclidean Distance Matrices ⋮ Iterative universal rigidity

Uses Software

• SFSDP

This page was built for publication: Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions