Optimization Online


An LP-based Algorithm to Test Copositivity

Akihiro Tanaka (tanaka.akihiro***at***sk.tsukuba.ac.jp)
Akiko Yoshise (yoshise***at***sk.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/2014
Entry Accepted: 04/27/2014
Entry Last Modified: 07/17/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society