Evaluating approximations of the semidefinite cone with trace normalized distance

Abstract

We evaluate the dual cone of the set of diagonally dominant matrices (resp., scaled diagonally dominant matrices), namely ${\mathcal{DD}}_n^{\ast }$ (resp., ${\mathcal{S}\mathcal{DD}}_n^{\ast }$), as an approximation of the semidefinite cone. We prove that the norm normalized distance, proposed by Blekherman et al. (2022), between a set $\mathcal{S}$ and the semidefinite cone has the same value whenever ${\mathcal{S}\mathcal{DD}}_n^{\ast }\subseteq \mathcal{S}\subseteq {\mathcal{DD}}_n^{\ast }$. This implies that the norm normalized distance is not a sufficient measure to evaluate these approximations. As a new measure to compensate for the weakness of that distance, we propose a new distance, called the trace normalized distance. We prove that the trace normalized distance between ${\mathcal{DD}}_n^{\ast }$ and ${\mathcal{S}}_{+}^n$ has a different value from the one between ${\mathcal{S}\mathcal{DD}}_n^{\ast }$ and ${\mathcal{S}}_{+}^n$ and give the exact values of these distances.

arXiv comment15 pages

References in corpus (4)

• Partial facial reduction: simplified, equivalent SDPs via approximations of the PSD cone
• On Polyhedral and Second-Order Cone Decompositions of Semidefinite Optimization Problems
• Polyhedral approximations of the semidefinite cone and their application
• On polyhedral approximations of the positive semidefinite cone