A symmetric matrix is called copositive if it generates a quadratic form taking no negative values over the nonnegative orthant, and the linear optimization problem over the set of copositive matrices is called the copositive programming problem. Recently, many studies have been done on the copositive programming problem (see, for example, \cite{aDUR10, aBOMZE12}). Among others, several branch and bound type algorithms have been provided to test copositivity in the context of the fact that deciding whether a given matrix is copositive is co-NP-complete \cite{aMURTY87,aDICKINSON14b}. In this paper, we propose a new branch and bound type algorithm for this testing problem based on Sponsel, Bundfuss and D\"{u}r's algorithm\cite{aSPONSEL12}. Two features of our algorithm are: (1) we introduce new classes of matrices $\mathcal{G}_n^s$ and $\widehat{\mathcal{G}_n^s}$ which are relatively large subsets of the set of copositive matrices and work well to check copositivity of a given $n \times n$ symmetric matrix, and (2) for incorporating the sets $\mathcal{G}_n^s$ or $\widehat{\mathcal{G}_n^s}$ in checking copositivity, we only have to solve a linear optimization problem with $n+1$ variables and $O(n^2)$ constraints after computing a singular value matrix decomposition, which implies that our algorithm is not so time-consuming. Our preliminary numerical experiments suggest that our algorithm is promising for determining upper bounds of the maximum clique problem.
Citation
Pacific Journal of Optimization, 11(2015), 101-120.