  


An LPbased Algorithm to Test Copositivity
Akihiro Tanaka (tanaka.akihirosk.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 coNPcomplete \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 timeconsuming. 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), 101120. Download: [PDF] Entry Submitted: 04/26/2014 Modify/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  