Minimum-rank positive semidefinite matrix completion with chordal patterns and applications to semidefinite relaxations

Xin Jiang, Yifan Sun, Martin Skovgaard Andersen, Lieven Vandenberghe

Research output: Contribution to journalJournal articleResearchpeer-review

133 Downloads (Pure)

Abstract

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 minimum-rank 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.
Original languageEnglish
JournalApplied Set-Valued Analysis and Optimization
Volume5
Issue number2
Pages (from-to)265-283
ISSN2562-7775
DOIs
Publication statusPublished - 2023

Keywords

  • Chordal graphs
  • Euclidean distance matrix
  • Matrix completion
  • Optimal power flow
  • Semidefinite optimization

Fingerprint

Dive into the research topics of 'Minimum-rank positive semidefinite matrix completion with chordal patterns and applications to semidefinite relaxations'. Together they form a unique fingerprint.

Cite this