AN INTERIOR-POINT METHOD FOR APPROXIMATE POSITIVE SEMIDEFINITE COMPLETIONS

Given a nonnegative, symmetric matrix of weights, H, we study the prob lem of finding an Hermitian, positive semidefinite matrix which is clo sest 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 unspecified (free), whi te H-ij large in absolute value corresponds to the element A(ij) being approximately specified (fixed). We present optimality conditions, du ality theory, and two primal-dual interior-point algorithms. Because o f sparsity considerations, the dual-step-first algorithm is more effic ient for a large number of free elements, while the primal-step-first algorithm is more efficient for a large number of fixed elements. Incl uded are numerical tests that illustrate the efficiency and robustness of the algorithms.