Comparing SOS and SDP relaxations of sensor network localization

João Gouveia; Ting Kei Pong

doi:10.1007/s10589-011-9431-1

Comparing SOS and SDP relaxations of sensor network localization

João Gouveia, Ting Kei Pong

Research output: Journal article publication › Journal article › Academic research › peer-review

4 Citations (Scopus)

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.

Original language	English
Pages (from-to)	609-627
Number of pages	19
Journal	Computational Optimization and Applications
Volume	52
Issue number	3
DOIs	https://doi.org/10.1007/s10589-011-9431-1
Publication status	Published - 1 Jul 2012
Externally published	Yes

Keywords

Individual trace
Semidefinite programming relaxation
Sensor network localization
Sum of squares relaxation

ASJC Scopus subject areas

Applied Mathematics
Computational Mathematics
Control and Optimization

More information

10.1007/s10589-011-9431-1

Cite this

@article{c6c42a101042489ea59e109a18053ac9,

title = "Comparing SOS and SDP relaxations of sensor network localization",

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.",

keywords = "Individual trace, Semidefinite programming relaxation, Sensor network localization, Sum of squares relaxation",

author = "Jo{\~a}o Gouveia and Pong, {Ting Kei}",

year = "2012",

month = jul,

day = "1",

doi = "10.1007/s10589-011-9431-1",

language = "English",

volume = "52",

pages = "609--627",

journal = "Computational Optimization and Applications",

issn = "0926-6003",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Comparing SOS and SDP relaxations of sensor network localization

AU - Gouveia, João

AU - Pong, Ting Kei

PY - 2012/7/1

Y1 - 2012/7/1

N2 - 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.

AB - 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.

KW - Individual trace

KW - Semidefinite programming relaxation

KW - Sensor network localization

KW - Sum of squares relaxation

UR - http://www.scopus.com/inward/record.url?scp=84865227856&partnerID=8YFLogxK

U2 - 10.1007/s10589-011-9431-1

DO - 10.1007/s10589-011-9431-1

M3 - Journal article

SN - 0926-6003

VL - 52

SP - 609

EP - 627

JO - Computational Optimization and Applications

JF - Computational Optimization and Applications

IS - 3

ER -

Comparing SOS and SDP relaxations of sensor network localization

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this