Henry Wolkowicz
Department of Combinatorics and Optimization
University of Waterloo
Waterloo, Ontario N2L 3G1

Abstract:

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 in order to make $A$ positive semidefinite. A very 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 in terms of existence of completions.

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.