Solving Euclidean distance matrix completion problems via semidefinite programming

Citation
Ay. Alfakih et al., Solving Euclidean distance matrix completion problems via semidefinite programming, COMPUT OP A, 12(1-3), 1999, pp. 13-30
Citations number
48
Categorie Soggetti
Engineering Mathematics
Journal title
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
ISSN journal
09266003 → ACNP
Volume
12
Issue
1-3
Year of publication
1999
Pages
13 - 30
Database
ISI
SICI code
0926-6003(199901)12:1-3<13:SEDMCP>2.0.ZU;2-E
Abstract
Given a partial symmetric matrix A with only certain elements specified, th e Euclidean distance matrix completion problem (EDMCP) is to find the unspe cified elements of A that make A a Euclidean distance matrix (EDM). In this paper, we follow the successful approach in [20] and solve the EDMCP by ge neralizing the completion problem to allow for approximate completions. In particular, we introduce a primal-dual interior-point algorithm that solves an equivalent (quadratic objective function) semidefinite programming prob lem (SDP). Numerical results are included which illustrate the efficiency a nd robustness of our approach. Our randomly generated problems consistently resulted in low dimensional solutions when no completion existed.