In this paper we construct new families of extremal copositive matrices in arbitrary dimension by an algorithmic procedure. Extremal copositive matrices are organized in relatively open subsets of real-algebraic varie...
详细信息
In this paper we construct new families of extremal copositive matrices in arbitrary dimension by an algorithmic procedure. Extremal copositive matrices are organized in relatively open subsets of real-algebraic varieties, and knowing a particular such matrix A allows in principle to obtain the variety in which A is embedded by solving the corresponding system of algebraic equations. We show that if A is a matrix associated to a so-called COP-irreducible graph with stability number equal 3, then by a trigonometric transformation these algebraic equations become linear and can be solved by linear algebra methods. We develop an algorithm to construct and solve the corresponding linear systems and give examples where the variety contains singularities at the initial matrix A. For the cycle graph C 7 we completely characterize the part of the variety which consists of copositive matrices. (c) 2023 Elsevier Inc. All rights reserved.
We provide convergent hierarchies for the convex cone of copositive matrices and its dual , the cone of completely positive matrices. In both cases the corresponding hierarchy consists of nested spectrahedra and provi...
详细信息
We provide convergent hierarchies for the convex cone of copositive matrices and its dual , the cone of completely positive matrices. In both cases the corresponding hierarchy consists of nested spectrahedra and provide outer (resp. inner) approximations for (resp. for its dual ), thus complementing previous inner (resp. outer) approximations for (for ). In particular, both inner and outer approximations have a very simple interpretation. Finally, extension to -copositivity and -complete positivity for a closed convex cone , is straightforward.
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 t...
详细信息
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 (T) over cap (-) = {y is an element of Delta(m)vertical bar beta(T)(y) <= 0} on the standard simplex Delta(m), where each component of the vector beta is -1, 0 or 1. (C) 2011 Elsevier Inc. All rights reserved.
The paper presents necessary and sufficient conditions that a symmetric matrix be copositive or strictly copositive. The conditions are given in terms of the eigenvalues and eigenvectors of the principal submatrices o...
详细信息
The paper presents necessary and sufficient conditions that a symmetric matrix be copositive or strictly copositive. The conditions are given in terms of the eigenvalues and eigenvectors of the principal submatrices of the given matrix. (C) 2000 Elsevier Science Inc. All rights reserved.
A symmetric matrix A is an element of R-nxn is called copositive if it satisfies the inequality x(T) Ax >= 0 whenever x >= 0 and strictly copositive if x(T) Ax > 0, whenever 0 not equal x >= 0. The orderin...
详细信息
A symmetric matrix A is an element of R-nxn is called copositive if it satisfies the inequality x(T) Ax >= 0 whenever x >= 0 and strictly copositive if x(T) Ax > 0, whenever 0 not equal x >= 0. The ordering of a vector here is component-wise. Certain interesting properties of the inverse of a copositive matrix are extended to its Moore-Penrose inverse. The inheritance property of the Schur complement of a copositive matrix is extended to the casewhenthe inverses in the Schur complement are replaced by their Moore-Penrose inverses. A framework is provided wherein one has the copositivity of B+ - A(+), given the copositivity of A - B.
There is a strong connection between copositive matrices and graph theory. copositive matrices provide a powerful tool for formulating and approximating various challenging graph-related problems. In return, graph the...
详细信息
There is a strong connection between copositive matrices and graph theory. copositive matrices provide a powerful tool for formulating and approximating various challenging graph-related problems. In return, graph theory offers a rich set of concepts and techniques that can be used to explore important properties of copositive matrices, such as their eigenvalues and spectra. This paper presents new insights into this interplay. Specifically, we focus on the set of all zeros of a copositive matrix, examining its properties and demonstrating that it can be expressed as a union of convex hulls of certain subsets of minimal zeros. We further show that these subsets are closely linked to the maximal cliques of a special graph, constructed based on the minimal zeros of the matrix. An algorithm is explicitly described for constructing the complete set of normalized zeros and minimal zeros of a copositive matrix. (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http:// ***/licenses/by/4.0/).
Copositivity plays a role in combinatorial and nonconvex quadratic optimization. However, testing copositivity of a given matrix is a co-NP-complete problem. We improve a previously given branch-and-bound type algorit...
详细信息
Copositivity plays a role in combinatorial and nonconvex quadratic optimization. However, testing copositivity of a given matrix is a co-NP-complete problem. We improve a previously given branch-and-bound type algorithm for testing copositivity and discuss its behavior in particular for the maximum clique problem. Numerical experiments indicate that the speedup is considerable.
We consider general, typically nonconvex, Quadratic Programming Problems. The Semi-definite relaxation proposed by Shor provides bounds on the optical solution. but it does not always provide sufficiently strong bound...
详细信息
We consider general, typically nonconvex, Quadratic Programming Problems. The Semi-definite relaxation proposed by Shor provides bounds on the optical solution. but it does not always provide sufficiently strong bounds if linear constraints are also involved. To get rid of the linear side-constraints. another, stronger convex relaxation is derived. This relaxation uses copositive matrices. Special cases are discussed for which both relaxations are equal. At the end of the paper, the complexity and solvability of the relaxations are discussed.
The convex cone of n x n completely positive (CP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CP matrix is doubly nonnegative (DNN), i...
详细信息
The convex cone of n x n completely positive (CP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for n <= 4 only, every DNN matrix is CP. In this paper, we investigate the difference between 5 x 5 DNN and CP matrices. Defining a bad matrix to be one which is DNN but not CP, we: (i) design a finite procedure to decompose any n x n DNN matrix into the sum of a CP matrix and a bad matrix, which itself cannot be further decomposed;(ii) show that every bad 5 x 5 DNN matrix is the sum of a CP matrix and a single bad extreme matrix;and (iii) demonstrate how to separate bad extreme matrices from the cone of 5 x 5 CP matrices. (C) 2009 Elsevier Inc. All rights reserved.
暂无评论