Quadratic-programming criteria for copositive matrices (Q1823293)

Finding out whether a real symmetric \(n\times n\) matrix A is not copositive is an NP-complete problem. Thus it is not surprising that there is not any efficient algorithm for determining the copositivity class of A. In the worst case, the computational effort required by the available matrix-theoretic criteria grows exponentially with n. In the paper the author derives some criteria for copositive, copositive- plus, and strictly copositive matrices based on quadratic programming. Suppose that a real symmetric \(n\times n\) matrix A contains a nonnegative definite principle submatrix of order n-p. In the case \(p=0\), linear programming techniques such as the phase one of the simplex method are sufficient to determine the compositivity of A. In the case \(p\geq 1\) quadratic programming procedure is required, and the ensuring quadratic program is convex for \(p=1\) and nonconvex for \(p>1\). Convex problems are solved by means of the simplex method for quadratic programming, and nonconvex problems by means of the parametric method for quadratic programming. The author also examines the determination of breaking rays for different copositivity classes, and reduces the determination of the copositivity- class of A to the determination of the copositivity classes of certain principle submatrices of A. The quadratic programming criteria are compared with some available matrix-theoretic criteria.