Blekherman Grigoriy

Sparse PSD approximation of the PSD cone

  • Santanu S. Dey
  • Blekherman Grigoriy
  • Marco Molinaro
  • Shengding Sun
    • Categories Global Optimization Theory, Semi-definite Programming Tags ,

    While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One technique to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k times k principal submatrices — we call this the sparse SDP relaxation. Surprisingly, … Read more