Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions - Mathematics > Optimization and ControlReportar como inadecuado




Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions - Mathematics > Optimization and Control - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: The sensor network localization, SNL, problem in embedding dimension r,consists of locating the positions of wireless sensors, given only thedistances between sensors that are within radio range and the positions of asubset of the sensors called anchors. Current solution techniques relax thisproblem to a weighted, nearest, positive semidefinite programming, SDP,completion problem, by using the linear mapping between Euclidean distancematrices, EDM, and semidefinite matrices. The resulting SDP is solved usingprimal-dual interior point solvers, yielding an expensive and inexact solution.This relaxation is highly degenerate in the sense that the feasible set isrestricted to a low dimensional face of the SDP cone, implying that the Slaterconstraint qualification fails. Cliques in the graph of the SNL problem giverise to this degeneracy in the SDP relaxation. In this paper, we take advantageof the absence of the Slater constraint qualification and derive a techniquefor the SNL problem, with exact data, that explicitly solves the correspondingrank restricted SDP problem. No SDP solvers are used. For randomly generatedinstances, we are able to efficiently solve many huge instances of this NP-hardproblem to high accuracy, by finding a representation of the minimal face ofthe SDP cone that contains the SDP matrix representation of the EDM. The mainwork of our algorithm consists in repeatedly finding the intersection ofsubspaces that represent the faces of the SDP cone that correspond to cliquesof the SNL problem.



Autor: Nathan Krislock, Henry Wolkowicz

Fuente: https://arxiv.org/



DESCARGAR PDF




Documentos relacionados