Tractable Subcones and LP-based Algorithms for Testing Copositivity
Tractable Subcones and LP-based Algorithms for Testing Copositivity
复制标题
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Akihiro Tanaka;Akiko Yoshise
中科院分区：
文献类型：
--
作者：
Akihiro Tanaka;Akiko Yoshise
作者在以前的文件设计了某些子锥的共正锥，并表明，可以检测是否一个给定的矩阵属于他们每个人通过解决线性优化问题（LP）O（n）变量和O（n 2）的约束。他们还设计了基于LP的算法，用于使用子锥来测试共正性。在本文中，他们详细地研究了子锥的性质，并探索了具有理想性质的同正锥的更好的子锥，引入了一个半正定基（SD基），它是由n（n + 1）=2个对称半正定矩阵组成的n n对称矩阵空间的基.使用SD的基础上，他们设计了两个新的子锥检测可以通过解决LP O（n 2）变量和O（n 2）的约束。新的子锥比上一篇文章中的子锥更大，并继承了它们的优良性质。作者还研究了这些子锥的效率在数值实验中。结果表明，子锥是很有前途的测试共正性。
The authors in a previous paper devised certain subcones of the copositive cone and showed that one can detect whether a given matrix belongs to each of them by solving linear optimization problems (LPs) with O(n) variables and O(n 2 ) constraints. They also devised LP-based algorithms for testing copositivity using the subcones. In this paper, they investigate the properties of the subcones in more detail and explore better subcones of the copositive cone having desirable properties.They introduce a semidenite basis (SD basis) that is a basis of the space of n n symmetric matrices consisting of n(n + 1)=2 symmetric semidefinite matrices. Using the SD basis, they devise two new subcones for which detection can be done by solving LPs with O(n 2 ) variables and O(n 2 ) constraints. The new subcones are larger than the ones in the previous paper and inherit their nice properties. The authors also examine the efficiency of those subcones in numerical experiments. The results show that the subcones are promising for testing copositivity.