An interior-point algorithms for the Euclidean distance matrix
Abdo Y. Alfakih and Amir Khandani and Henry Wolkowicz
Given a partial symmetric matrix $A$ with only certain elements
specified, the Euclidean distance matrix completion problem (EDMCP)
consists in finding the unspecified elements of $A$ in order to make
$A$ a Euclidean distance matrix (EDM). In this paper, we follow a
recent successful approach and solve the EDMCP by generalizing the
completion problem to allow for approximate completions. In
particular, we introduce a primal-dual interior-point algorithm for
both approximate and exact completion problems. We include numerical
tests that show that the algorithm is very efficient and robust.
This algorithm solves an equivalent semidefinite programming problem
(SDP). In particular, the algorithm uses a new search direction for
semidefinite programming introduced recently. This search direction
is based on a Gauss-Newton approach and requires no symmetrization.
Numerical results are included which illustrate the high efficiency
and robustness of the interior-point approach.
Research Report CORR 97-9,
University of Waterloo, Department of Combinatorics and Optimization,
Waterloo, Ontario N2L 3G1, Canada.