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