Scaling relationship between the copositive cone and Parrilo’s first level approximation

Research paper by Peter J. C. Dickinson, Mirjam Dür, Luuk Gijben, Roland Hildebrand

Indexed on: 21 Jul '12Published on: 21 Jul '12Published in: Optimization Letters


We investigate the relation between the cone \({\mathcal{C}^{n}}\) of n × n copositive matrices and the approximating cone \({\mathcal{K}_{n}^{1}}\) introduced by Parrilo. While these cones are known to be equal for n ≤ 4, we show that for n ≥ 5 they are not equal. This result is based on the fact that \({\mathcal{K}_{n}^{1}}\) is not invariant under diagonal scaling. We show that for any copositive matrix which is not the sum of a nonnegative and a positive semidefinite matrix we can find a scaling which is not in \({\mathcal{K}_{n}^{1}}\). In fact, we show that if all scaled versions of a matrix are contained in \({\mathcal{K}_{n}^{r}}\) for some fixed r, then the matrix must be in \({\mathcal{K}_{n}^{0}}\). For the 5 × 5 case, we show the more surprising result that we can scale any copositive matrix X into \({\mathcal{K}_{5}^{1}}\) and in fact that any scaling D such that \({(DXD)_{ii} \in \{0,1\}}\) for all i yields \({DXD \in \mathcal{K}_{5}^{1}}\). From this we are able to use the cone \({\mathcal{K}_{5}^{1}}\) to check if any order 5 matrix is copositive. Another consequence of this is a complete characterisation of \({\mathcal{C}^{5}}\) in terms of \({\mathcal{K}_{5}^{1}}\). We end the paper by formulating several conjectures.