MINIMUM-RANK POSITIVE SEMIDEFINITE MATRIX COMPLETION WITH CHORDAL PATTERNS AND APPLICATIONS TO SEMIDEFINITE RELAXATIONS

We present an algorithm for computing the minimum-rank positive semidefinite completion of a sparse matrix with a chordal sparsity pattern. This problem is tractable, in contrast to the minimumrank positive semidefinite completion problem for general sparsity patterns. We also present a similar algorithm for the Euclidean distance matrix completion with minimum embedding dimension. The two algorithms use efficient recursions over a clique tree associated with the chordal sparsity pattern. As an application, we use the minimum-rank completion method as a rounding technique to convert the solution of a sparse semidefinite optimization problem with non-unique solutions to an optimal solution of lower rank. In experiments with semidefinite relaxations of optimal power flow problems, the minimum-rank completion often results in solutions of lower rank than the solutions computed by interior-point solvers.