Semidefinite Programming and Matrix Completion

plenary talk at the One-day Optimization Workshop, at McMaster University, Aug. 4, 2000, in the JHE building, room A114.

(The Abstract (text file):; the presentation (ps file))

This talk is partly based on several papers; principally, on the papers
dealing with completion problems.
The paper

Positive definite completions of
partial {H}ermitian matrices
(GRONE, B. and JOHNSON, C.R. and MARQUES de SA, E. and WOLKOWICZ, H.)
presents a characterization for completion using chordality of graphs;

while the two papers:

AN INTERIOR-POINT METHOD FOR APPROXIMATE POSITIVE
SEMIDEFINITE COMPLETIONS and

Solving Euclidean distance matrix completion problems via
semidefinite programming

present primal-dual interior-point methods for solving approximate
completion problems. A summary of these results is presented in

Matrix Completion Problems, in the
Handbook of Semidefinite Programming, Kluwer Academic, 2000.
A new summary with new results on the EDM completion problem is
in the CORR report
Semidefinite Programming for Discrete Optimization and Matrix Completion
Problems, June, 2000