Quadratic-programming criteria for copositive matrices (Q1823293): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:48, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Quadratic-programming criteria for copositive matrices |
scientific article |
Statements
Quadratic-programming criteria for copositive matrices (English)
0 references
1989
0 references
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.
0 references
NP-complete problem
0 references
algorithm
0 references
copositive-plus
0 references
copositive matrices
0 references
quadratic programming
0 references
linear programming
0 references
simplex method
0 references