Semidefinite Programming and Matrix Completion Problems<p>

   Henry Wolkowicz<br>
 Department of Combinatorics and Optimization<br>
 University of Waterloo<br>
 Waterloo, Ontario  N2L 3G1<br>
<p>

Suppose we are given a partial Hermitian matrix $A$
with certain elements fixed, for
which all fully specified (fixed)  principal submatrices are positive
semidefinite.
The positive semidefinite completion problem consists in
finding numbers for the unspecified (free)
elements to make $A$ positive
semidefinite. 
A closely related problem is the Euclidean distance
matrix completion problem, i.e. the problem of finding the unspecified
elements of $A$ that make $A$ a Euclidean distance matrix.
Both problems have many applications and
have been extensively studied.
Much is known about existence of
completions. 
<p>
In this talk we will look at both these problems and transform them into
approximate completion problems.
We will show that this transformation allows for efficient solutions
using semidefinite programming and interior-point methods. The
current methods for the positive semidefinite completion problem take
advantage of sparsity and can solve {\em large}, sparse problems.
However, the direct extension to the Euclidean distance matrix
completion problem does not take advantage of sparsity directly. We
present a new semidefinite programming characterization 
of the Euclidean distance matrix problem and use this to derive
an algorithm that can exploit sparsity.