An interior-point method for approximate positive semidefinite completions

Charles R. Johnson, Brenda Kroschel, Henry Wolkowicz

Given a nonnegative, symmetric matrix of weights, $H$, we study the problem of finding an Hermitian, positive semidefinite matrix which is closest to a given Hermitian matrix, $A,$ with respect to the weighting $H.$ This extends the notion of exact matrix completion problems in that, $H_{ij}=0$ corresponds to the element $A_{ij}$ being {\em unspecified} (free), while $H_{ij}$We present optimality conditions, duality theory, and two primal-dual interior-point algorithms. Because of sparsity considerations, the dual-step-first algorithm is more efficient for a large number of free elements, while the primal-step-first algorithm is more efficient for a large number of fixed elements. Included are numerical tests that illustrate the efficiency and robustness of the algorithms.

University of Waterloo, CORR Report 95-11.