On the quality of the k-PSD closure approximation

arXiv2105.11920MaRDI QIDQ6368487FDOQ6368487

Authors: Avinash Bhardwaj, Harshit N. Kothari, Vishnu Narayanan 

Publication date: 25 May 2021

Abstract: Postive semidefinite (PSD) cone is the cone of positive semidefinite matrices, and is the object of interest in semidefinite programming (SDP). A computational efficient approximation of the PSD cone is the $k$-PSD closure, $1leqk<n$, cone of $nimesn$ real symmetric matrices such that all of their $kimesk$ principal submatrices are positive semidefinite. For $k=1$, one obtains a polyhedral approximation, while $k=2$ yields a second order conic (SOC) approximation of the PSD cone. These approximations of the PSD cone have been used extensively in real-world applications such as AC Optimal Power Flow (ACOPF) to address computational inefficiencies where SDP relaxations are utilized for convexification the non-convexities. In a recent series of articles Blekharman et al. provided bounds on the quality of these approximations. In this work, we revisit some of their results and also propose a new dominant bound on quality of the $k$-PSD closure approximation of the PSD cone. In addition, we characterize the extreme rays of the $2$-PSD closure.

Mathematics Subject Classification ID

Semidefinite programming (90C22) Approximation by convex sets (52A27)

This page was built for publication: On the quality of the $k-$PSD closure approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6368487)