Algorithmic copositivity detection by simplicial partition (Q2477530): Difference between revisions

Let \({\mathcal S}\) denote the set of symmetric matrices in \({\mathbb R}^{n\times n}\), and let \({\mathbb R}^n_+\) be the nonnegative orthant. A matrix \(A\in {\mathcal S}\) is called copositive if \(x^T Ax \geq 0\) for all \(x\in {\mathbb R}^n_+\). Let \({\mathcal C}\) be the set of symmetric copositive matrices in \({\mathbb R}^{n\times n}\). For \(A\in{\mathcal S}\) let \({\mathcal P}=\{\Delta^1,\dots,\Delta^m\}\) be a simplicial partition of the standard simplex \(\Delta^S\) into \(m\) simplices, and let \(v^k_1,\dots,v^k_n\) denote the vertices of the simplex \(\Delta^k\). Let \(k\in\{1,\dots,m\}\) and \(i,j\in\{1,\dots,n\}\). The authors show, if \((v^k_i)^TAv^k_j\geq 0\) for all \(k,i,j\), then \(A\) is copositive. If the inequality is strict, then \(A\) is strictly copositive. Let \(\delta({\mathcal P})\) be the maximum diameter of a simplex in the partition \({\mathcal P}\). If \(A\in{\mathcal S}\) is strictly copositive, then there is some \(\varepsilon>0\) such that for all finite simplicial partitions \({\mathcal P}=\{\Delta^1,\dots,\Delta^m\}\) of \(\Delta^S\) with \(\delta({\mathcal P})\leq\varepsilon\), we have \((v^k_i)^TAv^k_j> 0\) for all \(k=1,\dots,m\) and \(i,j=1,\ldots,n\), where \(v^k_1,\dots,v^k_n\) denote the vertices of the simplex \(\Delta^k\). The authors give algorithms, the first to determine if a matrix \(A\) is copositive, the second if it is \(\varepsilon\)-copositive, and the third for a subdivision of a simplex. They consider several numerical aspects.