Geometry of the copositive and completely positive cones

The copositive cone, and its dual the completely positive cone, have useful applications in optimisation, however telling if a general matrix is in the copositive cone is a co-NP-complete problem. In this paper we analyse some of the geometry of these cones. We discuss a way of representing all the maximal faces of the copositive cone along with a simple equation for the dimension of each one. In doing this we show that the copositive cone has faces which are isomorphic to positive semidefinite cones. We also look at some maximal faces of the completely positive cone and find their dimensions. Additionally we consider extreme rays of the copositive and completely positive cones and show that every extreme ray of the completely positive cone is also an exposed ray, but the copositive cone has extreme rays which are not exposed rays.     

Completely positive reformulations for polynomial optimization

Polynomial optimization encompasses a very rich class of problems in which both the objective and constraints can be written in terms of polynomials on the decision variables. There is a well established body of research on quadratic polynomial optimization problems based on reformulations of the original problem as a conic program over the cone of completely positive matrices, or its conic dual, the cone of copositive matrices. As a result of this reformulation approach, novel solution schemes for quadratic polynomial optimization problems have been designed by drawing on conic programming tools, and the extensively studied cones of completely positive and of copositive matrices. In particular, this approach has been applied to solve key combinatorial optimization problems. Along this line of research, we consider polynomial optimization problems that are not necessarily quadratic. For this purpose, we use a natural extension of the cone of completely positive matrices; namely, the cone of completely positive tensors. We provide a general characterization of the class of polynomial optimization problems that can be formulated as a conic program over the cone of completely positive tensors. As a consequence of this characterization, it follows that recent related results for quadratic problems can be further strengthened and generalized to higher order polynomial optimization problems. Also, we show that the conditions underlying the characterization are conceptually the same, regardless of the degree of the polynomials defining the problem. To illustrate our results, we discuss in further detail special and relevant instances of polynomial optimization problems.     

On the computational complexity of membership problems for the completely positive cone and its dual

Copositive programming has become a useful tool in dealing with all sorts of optimisation problems. It has however been shown by Murty and Kabadi (Math. Program. 39(2):117–129, 1987) that the strong membership problem for the copositive cone, that is deciding whether or not a given matrix is in the copositive cone, is a co-NP-complete problem. From this it has long been assumed that this implies that the question of whether or not the strong membership problem for the dual of the copositive cone, the completely positive cone, is also an NP-hard problem. However, the technical details for this have not previously been looked at to confirm that this is true. In this paper it is proven that the strong membership problem for the completely positive cone is indeed NP-hard. Furthermore, it is shown that even the weak membership problems for both of these cones are NP-hard. We also present an alternative proof of the NP-hardness of the strong membership problem for the copositive cone.     

Algorithmic copositivity detection by simplicial partition

We present new criteria for copositivity of a matrix, i.e., conditions which ensure that the quadratic form induced by the matrix is nonnegative over the nonnegative orthant. These criteria arise from the representation of the quadratic form in barycentric coordinates with respect to the standard simplex and simplicial partitions thereof. We show that, as the partition gets finer and finer, the conditions eventually capture all strictly copositive matrices. We propose an algorithmic implementation which considers several numerical aspects. As an application, we present results on the maximum clique problem. We also briefly discuss extensions of our approach to copositivity with respect to arbitrary polyhedral cones.     

Think co(mpletely)positive ! Matrix properties,examples and a clustered bibliography on copositive optimization

Copositive optimization is a quickly expanding scientific research domain with wide-spread applications ranging from global nonconvex problems in engineering to NP-hard combinatorial optimization. It falls into the category of conic programming (optimizing a linear functional over a convex cone subject to linear constraints), namely the cone C{\mathcal{C}} of all completely positive symmetric n × n matrices (which can be factorized into FF^T{FF^\top} , where F is a rectangular matrix with no negative entry), and its dual cone C^*{\mathcal{C}^*} , which coincides with the cone of all copositive matrices (those which generate a quadratic form taking no negative value over the positive orthant). We provide structural algebraic properties of these cones, and numerous (counter-)examples which demonstrate that many relations familiar from semidefinite optimization may fail in the copositive context, illustrating the transition from polynomial-time to NP-hard worst-case behaviour. In course of this development we also present a systematic construction principle for non-attainability phenomena, which apparently has not been noted before in an explicit way. Last but not least, also seemingly for the first time, a somehow systematic clustering of the vast and scattered literature is attempted in this paper.     

Quadratic factorization heuristics for copositive programming

Copositive optimization problems are particular conic programs: optimize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising.     

New results on the cp-rank and related properties of co(mpletely )positive matrices

Copositive and completely positive matrices play an increasingly important role in Applied Mathematics, namely as a key concept for approximating NP-hard optimization problems. The cone of copositive matrices of a given order and the cone of completely positive matrices of the same order are dual to each other with respect to the standard scalar product on the space of symmetric matrices. This paper establishes some new relations between orthogonal pairs of such matrices lying on the boundary of either cone. As a consequence, we can establish an improvement on the upper bound of the cp-rank of completely positive matrices of general order and a further improvement for such matrices of order six.     

判定3,4或5阶对称矩阵偕正性的算法

文献[1]给出了判定阶数不大于5的对称矩阵偕正性的充分必要条件.本文在此基础上,进一步给出了它们严格偕正的条件,并提出了三个算法,它们能够用来有效地判定3,4,5阶对称矩阵严格偕正、偕正或非偕正.     

On copositive matrices with −1, 0, 1 entries

Let $\text{E}$ be the set of symmetric matrices in which every entry is 0 or ±1 and each diagonal entry is 1. We characterize those matrices in $\text{E}$ which are, respectively, (a) copositive, (b) copositive-plus, (c) positive semidefinite. We characterize those copositive matrices in $\text{E}$ which are on extreme rays of the cone of copositive matrices. We give a counterexample to a conjecture of L. D. Baumert about zeros of copositive matrices.     

Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation

We present a decomposition-approximation method for generating convex relaxations for nonconvex quadratically constrained quadratic programming (QCQP). We first develop a general conic program relaxation for QCQP based on a matrix decomposition scheme and polyhedral (piecewise linear) underestimation. By employing suitable matrix cones, we then show that the convex conic relaxation can be reduced to a semidefinite programming (SDP) problem. In particular, we investigate polyhedral underestimations for several classes of matrix cones, including the cones of rank-1 and rank-2 matrices, the cone generated by the coefficient matrices, the cone of positive semidefinite matrices and the cones induced by rank-2 semidefinite inequalities. We demonstrate that in general the new SDP relaxations can generate lower bounds at least as tight as the best known SDP relaxations for QCQP. Moreover, we give examples for which tighter lower bounds can be generated by the new SDP relaxations. We also report comparison results of different convex relaxation schemes for nonconvex QCQP with convex quadratic/linear constraints, nonconvex quadratic constraints and 0–1 constraints.     

On Copositive Programming and Standard Quadratic Optimization Problems

A standard quadratic problem consists of finding global maximizers of a quadratic form over the standard simplex. In this paper, the usual semidefinite programming relaxation is strengthened by replacing the cone of positive semidefinite matrices by the cone of completely positive matrices (the positive semidefinite matrices which allow a factorization FF ^T where F is some non-negative matrix). The dual of this cone is the cone of copositive matrices (i.e., those matrices which yield a non-negative quadratic form on the positive orthant). This conic formulation allows us to employ primal-dual affine-scaling directions. Furthermore, these approaches are combined with an evolutionary dynamics algorithm which generates primal-feasible paths along which the objective is monotonically improved until a local solution is reached. In particular, the primal-dual affine scaling directions are used to escape from local maxima encountered during the evolutionary dynamics phase.     

A note on Burer’s copositive representation of mixed-binary QPs

In an important paper, Burer (Math. Program Ser. A 120:479–495, 2009) recently showed how to reformulate general mixed-binary quadratic optimization problems (QPs) into copositive programs where a linear functional is minimized over a linearly constrained subset of the cone of completely positive matrices. In this note we interpret the implication from a topological point of view, showing that the Minkowski sum of the lifted feasible set and the lifted recession cone gives exactly the closure of the former. We also discuss why feasibility of the copositive program implies feasibility of the original mixed-binary QP, which can be derived from the arguments in Burer (Math. Program Ser. A 120:479–495, 2009) without any further condition.     

The difference between doubly nonnegative and completely positive matrices

The convex cone of n×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 n4 only, every DNN matrix is CP. In this paper, we investigate the difference between 5×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×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×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×5 CP matrices.     

On the convergence of iterative methods for symmetric linear complementarity problems

We prove convergence of the whole sequence generated by any of a large class of iterative algorithms for the symmetric linear complementarity problem (LCP), under the only hypothesis that a quadratic form associated with the LCP is bounded below on the nonnegative orthant. This hypothesis holds when the matrix is strictly copositive, and also when the matrix is copositive plus and the LCP is feasible. The proof is based upon the linear convergence rate of the sequence of functional values of the quadratic form. As a by-product, we obtain a decomposition result for copositive plus matrices. Finally, we prove that the distance from the generated sequence to the solution set (and the sequence itself, if its limit is a locally unique solution) have a linear rate of R-convergence.Research for this work was partially supported by CNPq grant No. 301280/86.     

Generalized linear complementarity problems

It has been shown by Lemke that if a matrix is copositive plus on ⁿ , then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350.     

Spectrahedral cones generated by rank 1 matrices

Let \(\mathcal{S}_+^n \subset \mathcal{S}^n\) be the cone of positive semi-definite matrices as a subset of the vector space of real symmetric \(n \times n\) matrices. The intersection of \(\mathcal{S}_+^n\) with a linear subspace of \(\mathcal{S}^n\) is called a spectrahedral cone. We consider spectrahedral cones K such that every element of K can be represented as a sum of rank 1 matrices in K. We shall call such spectrahedral cones rank one generated (ROG). We show that ROG cones which are linearly isomorphic as convex cones are also isomorphic as linear sections of the positive semi-definite matrix cone, which is not the case for general spectrahedral cones. We give many examples of ROG cones and show how to construct new ROG cones from given ones by different procedures. We provide classifications of some subclasses of ROG cones, in particular, we classify all ROG cones for matrix sizes not exceeding 4. Further we prove some results on the structure of ROG cones. We also briefly consider the case of complex or quaternionic matrices. ROG cones are in close relation with the exactness of semi-definite relaxations of quadratically constrained quadratic optimization problems or of relaxations approximating the cone of nonnegative functions in squared functional systems.     

对称双正型线性互补问题的多重网格迭代解收敛性理论

多重网格法是七十年代产生并获得迅速发展的快速送代法.八十年代初,此方法开始应用于变分不等式的求解,其中包括一类互补问题,近十年来大量的数值实验证实,算法是成功的,而算法的收敛性理论也正在逐步建立,当A正定对称时的多重网格收敛性可见[3]和[7];[4]讨论了A半正定时的情况·本文考虑A为更广的一类矩阵:对称双正阵(见定义1.1),建立互补问题:     

On copositive matrices

A criterion for copositive matrices is given and for n = 3 the set of all copositive matrices is determined in terms of matrix elements. Copositive matrices are applied to the problem of excluding periodic solutions of certain algebraic differential equations.     

Ordering Epic R-fields

We are concerned with the following problem. Given a ring R and an epic R-field K, under what conditions can K be fully ordered? Epic R-fields can be constructed in terms of matrices over R; this makes it natural to consider matrix cones over R rather than ordinary cones of elements of K. Essentially, a matrix cone over R, associated with a given ordering of K, consists of all square matrices which either become singular or have positive Dieudonné determinant over K. We give necessary and sufficient conditions in terms of matrix cones for (i) an epic R-field to be orderable, (ii) a full order on R to be extendable to a field of fractions of R and (iii) for such an extension to be unique.     

Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones

We describe an implementation of nonsymmetric interior-point methods for linear cone programs defined by two types of matrix cones: the cone of positive semidefinite matrices with a given chordal sparsity pattern and its dual cone, the cone of chordal sparse matrices that have a positive semidefinite completion. The implementation takes advantage of fast recursive algorithms for evaluating the function values and derivatives of the logarithmic barrier functions for these cones. We present experimental results of two implementations, one of which is based on an augmented system approach, and a comparison with publicly available interior-point solvers for semidefinite programming.