An algorithm for determining copositive matrices

DOI10.1016/J.LAA.2011.04.038zbMATH Open1225.65048arXiv1011.2039OpenAlexW2963341325MaRDI QIDQ636239FDOQ636239

Yong Yao, Jia Xu

Publication date: 26 August 2011

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: In this paper, we present an algorithm of simple exponential growth called COPOMATRIX for determining the copositivity of a real symmetric matrix. The core of this algorithm is a decomposition theorem, which is used to deal with simplicial subdivision of $$ on the standard simplex $Delt{a}_m$, where each component of the vector $$ is -1, 0 or 1.

Full work available at URL: https://arxiv.org/abs/1011.2039

Recommendations

• Algorithmic copositivity detection by simplicial partition
• A modified simplex partition algorithm to test copositivity
• Algorithms for determining the copositivity of a given symmetric matrix
• A copositivity probe
• A note on algorithms for determining the copositivity of a given symmetric matrix

zbMATH Keywords

copositive matricescomplete algorithmcopositive quadratic formssimplicial subdivision of convex polytope

Mathematics Subject Classification ID

Hermitian, skew-Hermitian, and related matrices (15B57) Positive matrices and their generalizations; cones of matrices (15B48) Quadratic and bilinear forms, inner products (15A63)

Cites Work

• Some NP-complete problems in quadratic and nonlinear programming
• Partial cylindrical algebraic decomposition for quantifier elimination
• On the copositive representation of binary and continuous nonconvex quadratic programs
• Approximation of the stability number of a graph via copositive programming
• Bimatrix Equilibrium Points and Mathematical Programming
• Title not available (Why is that?)
• Algorithms in real algebraic geometry
• On copositive matrices with -1, 9, 1 entries
• Two remarks on copositive matrices
• The copositive completion problem
• Criteria for copositive matrices
• A test for copositive matrices
• On copositive matrices
• On classes of copositive matrices
• Title not available (Why is that?)
• Positive polynomials and sums of squares
• Title not available (Why is that?)
• Copositive matrices and definiteness of quadratic forms subject to homogeneous linear inequality constraints
• Criteria for copositive matrices of order four
• Algorithmic copositivity detection by simplicial partition
• Linear-Time Copositivity Detection for Tridiagonal Matrices and Extension to Block-Tridiagonality
• Title not available (Why is that?)
• On copositive programming and standard quadratic optimization problems
• Title not available (Why is that?)
• Recent advances in automated theorem proving on inequalities
• Title not available (Why is that?)
• Quadratic-programming criteria for copositive matrices
• Algorithms for determining the copositivity of a given symmetric matrix
• Block pivoting and shortcut strategies for detecting copositivity
• Copositive realxation for genera quadratic programming
• Constructing copositive matrices from interior matrices
• Criteria for copositive matrices using simplices and barycentric coordinates
• Role of copositivity in optimality criteria for nonconvex optimization problems
• Testing the definiteness of matrices on polyhedral cones
• Finite criteria for conditional definiteness of quadratic forms
• Copositive matrices and Simpson's paradox
• Conditionally definite matrices
• Spectral theory of copositive matrices
• Title not available (Why is that?)
• A copositivity probe
• Arbitrarily weak linear convexity conditions for multivariate polynomials
• Title not available (Why is that?)

Cited In (9)

• Algorithms for determining the copositivity of a given symmetric matrix
• Title not available (Why is that?)
• Quadratic-programming criteria for copositive matrices
• Copositivity detection of tensors: theory and algorithm
• A copositivity probe
• On copositiveness identification of partially symmetric rectangular tensors
• Title not available (Why is that?)
• A test for copositive matrices
• Copositive tensor detection and its applications in physics and hypergraphs

Uses Software

• Maple
• QEPCAD

This page was built for publication: An algorithm for determining copositive matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q636239)