Evaluating approximations of the semidefinite cone with trace normalized distance

Yuzhu Wang (wangyuzhu820yahoo.co.jp)
Akiko Yoshise (yoshisesk.tsukuba.ac.jp)

Abstract: We evaluate the dual cone of the set of diagonally dominant matrices (resp., scaled diagonally dominant matrices), namely ${\cal DD}_n^*$ (resp., ${\cal SDD}_n^*$), as an approximation of the semidefinite cone. Using the measure proposed by Blekherman et al. (2020) called norm normalized distance, we prove that the norm normalized distance between a set ${\cal S}$ and the semidefinite cone has the same value whenever ${\cal SDD}_n^* \subseteq {\cal S} \subseteq {\cal DD}_n^*$. 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 trace normalized distance. We prove that the trace normalized distance between ${\cal DD}_n^*$ and ${\cal S}^n_+$ has a different value from the one between ${\cal SDD}_n^*$ and ${\cal S}^n_+$, and give the exact values of these distances.

Keywords: Semidefinite optimization problem; Diagonally dominant matrix; Scaled diagonally dominant matrix.

Category 1: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Discussion Paper Series, No.1376, Department of Policy and Planning Sciences, University of Tsukuba

Download: [PDF]

Entry Submitted: 05/28/2021
Entry Accepted: 05/29/2021
Entry Last Modified: 05/30/2021

Modify/Update this entry