Algorithms for determining the copositivity of a given symmetric matrix
Copositive matrices are important in matrix theory and its applications. Many paper are dealing with quick algorithms of determining copositivity of a given symmetric matrix. The reason of the wide interest in this topic are applications in numerical methods concerning large linear system solution or related eigenvalue problems. The general problem of testing for co-positivity of a real symmetric matrix \(\mathbf A \in \mathbb R^{m\times n}\) represents an NP-complete problem defined by the same authors in previous papers. The authors conclude that a fully general algorithm for determining the copositivity of a matrix \(\mathbf A\) does not exist until now. Some sub-classes of matrices \(\mathbf A\) only can be treated as it follows from several references. The paper in question provides five new algorithms for matrices of order 3-7 giving quickly the complete answer for the test of copositivity with a following resolution: not copositive, copositive, strictly copositive. The sixth algorithm is developed for matrices of order \(n\geq 8\). Although it does not guarantee that a unique answer will be provided, a still acceptable result is mostly given. If it exceptionally fails, adequate information is reported. All steps are carefully substantiated. Deduction proceeds with caution in a form of theorems and corollaries (including proofs) utilizing results of earlier publications. Implementation of algorithms and their realization in a MATLAB form are described in details. Comprehensive numerical experiments are done together with transparent interpretation. Computational effectivity and reliability are evaluated. The list of references is large enough referencing many papers appeared in recent time related directly with the topic itself (including one self-reference) as well as some resources noticing historical backgrounds of the problem.
- A copositivity probe
- A test for copositive matrices
- Copositive matrices and Simpson's paradox
- Criteria for copositive matrices
- Criteria for copositive matrices using simplices and barycentric coordinates
- On copositive matrices
- Quadratic-programming criteria for copositive matrices
- Some NP-complete problems in quadratic and nonlinear programming
- Spectral theory of copositive matrices
- The copositive completion problem
- Criteria for copositive matrices of order four
- Quadratic-programming criteria for copositive matrices
- Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
- On monotonicity and search strategies in face-based copositivity detection algorithms
- On sparsity of the solution to a random quadratic optimization problem
- Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme
- Criteria for copositive matrices
- Depth-first simplicial partition for copositivity detection, with an application to MaxClique
- scientific article; zbMATH DE number 4174235 (Why is no real title available?)
- New Analysis on Sparse Solutions to Random Standard Quadratic Optimization Problems and Extensions
- Sparse solutions to random standard quadratic optimization problems
- Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization
- Optimality conditions for linear copositive programming problems with isolated immobile indices
- A copositivity probe
- An algorithm for determining copositive matrices
- A note on algorithms for determining the copositivity of a given symmetric matrix
This page was built for publication: Algorithms for determining the copositivity of a given symmetric matrix
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q959864)
