- An LP-based Algorithm to Test Copositivity Akihiro Tanaka (tanaka.akihirosk.tsukuba.ac.jp) Akiko Yoshise (yoshisesk.tsukuba.ac.jp) Abstract: 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. Keywords: Copositive programming, Matrix decomposition, Linear programming, Branch and bound algorithm, Maximum clique problem Category 1: Linear, Cone and Semidefinite Programming Citation: Pacific Journal of Optimization, 11(2015), 101-120. Download: [PDF]Entry Submitted: 04/26/2014Entry Accepted: 04/27/2014Entry Last Modified: 07/17/2016Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.