An Interior Point Method for Approximate Positive Semidefinite Completions

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 unspecified (free), while H_ij large in absolute value corresponds to the element A_ij being approximately specified (fixed). 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.