-

 

 

 




Optimization Online





 

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

Dickinson Peter J.C.(P.J.C.Dickinson***at***rug.nl)
Duer Mirjam(duer***at***uni-trier.de)
Luuk Gijben(L.Gijben***at***rug.nl)
Roland Hildebrand(roland.hildebrand***at***imag.fr)

Abstract: We investigate the relation between the cone of $n\times n$ copositive matrices and the approximating cone $\mathcal{K}^1$ introduced by Parrilo. While these cones are known to be equal for $n\leq 4$, we show that for $n \geq 5$ they are unequal. This result is based on the fact that $\mathcal{K}^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}^1$. In fact, we show that if all scaled versions of a matrix are contained in $\mathcal{K}^r$ for some fixed $r$, then the matrix must be in $\mathcal{K}^0$. For the $5\times 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 the $5\times 5$ copositive cone in terms of $\mathcal{K}_5^1$. We end the paper by formulating several conjectures.

Keywords: copositive cone, Parrilo's approximations, sum-of-squares conditions, $5\times 5$ copositive matrices

Category 1: Linear, Cone and Semidefinite Programming (Other )

Citation: Preprint, 2012

Download: [PDF]

Entry Submitted: 03/19/2012
Entry Accepted: 03/19/2012
Entry Last Modified: 03/19/2012

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society