Algorithmic copositivity detection by simplicial partition

DOI10.1016/J.LAA.2007.09.035MaRDI QIDQ2477530zbMATH OpenOpenAlexFDO

Publication date 14 March 2008

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.laa.2007.09.035

algorithms conditionally definite matrices copositive matrices simplicial partition

Quadratic and bilinear forms, inner products (15A63) Positive matrices and their generalizations; cones of matrices (15B48)

Review text

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.

Recommendations

Cites work

Cited in

(48)

This page was built for publication: Algorithmic copositivity detection by simplicial partition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2477530)