psd matrix completion

Faces of homogeneous cones and applications to homogeneous chordality

  • João Gouveia
  • Masaru Ito
  • Bruno F. Lourenço
    • Categories Cone Programming, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    A convex cone K is said to be homogeneous if its group of automorphisms acts transitively on its relative interior. Important examples of homogeneous cones include symmetric cones and cones of positive semidefinite (PSD) matrices that follow a sparsity pattern given by a homogeneous chordal graph. Our goal in this paper is to elucidate the … Read more

    Complexity of the positive semidefinite matrix completion problem with a rank constraint

  • Marianna Eisenberg-Nagy
  • Monique Laurent
  • Antonios Varvitsiotis
    • Categories Combinatorial Optimization, Semi-definite Programming Tags ,

    We consider the decision problem asking whether a partial rational symmetric matrix with an all-ones diagonal can be completed to a full positive semidefinite matrix of rank at most $k$. We show that this problem is $\NP$-hard for any fixed integer $k\ge 2$. Equivalently, for $k\ge 2$, it is $\NP$-hard to test membership in the … Read more