An interior-point algorithms for the Euclidean distance matrix completion problem

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.