A real symmetric matrix $A$ is copositive if $x^\top Ax\geq 0$ for all $x\geq 0$. As $A$ is copositive if and only if it is copositive on the standard simplex, algorithms to determine copositivity, such as those in Sponsel et al. (J Glob Optim 52:537–551, 2012) and Tanaka and Yoshise (Pac J Optim 11:101–120, 2015) are based upon the creation of increasingly fine simplicial partitions of simplices, testing for copositivity on each. We present a variant that decomposes a simplex $\Delta$, say with $n$ vertices, into a simplex $\Delta_1$ and a polyhedron $\Omega_1$; and then partitions $\Omega_1$ into a set of at most $(n-1)$ simplices. We show that if $A$ is copositive on $\Omega_1$ then $A$ is copositive on $\Delta_1$, allowing us to remove $\Delta_1$ from further consideration. Numerical results from examples that arise from the maximum clique problem show a significant reduction in the time needed to establish copositivity of matrices.
Citation
Mohammadreza Safi, Seyed Saeed Nabavi, and Richard J. Caron, “A Modified Simplex Partition Algorithm to Test Copositivity”, Journal of Global Optimization, 10.1007/s10898-021-01092-1, 2021-09-24 https://doi.org/10.1007/s10898-021-01092-1
Article
View A Modified Simplex Partition Algorithm to Test Copositivity