A real symmetric matrix $A$ is copositive if $x^\top Ax\geq 0$ for all $x\geq 0$. As $A$ is copositive if and only if it is copositive on the standard simplex, algorithms to determine copositivity, such as those in Sponsel et al. (J Glob Optim 52:537–551, 2012) and Tanaka and Yoshise (Pac J Optim 11:101–120, 2015) … Read more
Matrix copositivity has an important theoretical background. Over the last decades, the use of algorithms to check copositivity has made a big progress. Methods are based on spatial branch and bound, transformation to Mixed Integer Programming, implicit enumeration of KKT points or face-based search. Our research question focuses on exploiting the mathematical properties of the … Read more
We describe a simple method to test if a given matrix is copositive by solving a single mixed-integer linear programming (MILP) problem. This methodology requires no special coding to implement and takes advantage of the computational power of modern MILP solvers. Numerical experiments demonstrate that the method is robust and efficient. CitationDept. of Business Analytics, … Read more
We decompose the copositive cone $\copos{n}$ into a disjoint union of a finite number of open subsets $S_{\cal E}$ of algebraic sets $Z_{\cal E}$. Each set $S_{\cal E}$ consists of interiors of faces of $\copos{n}$. On each irreducible component of $Z_{\cal E}$ these faces generically have the same dimension. Each algebraic set $Z_{\cal E}$ is … Read more
We provide a complete classification of the extreme rays of the $6 \times 6$ copositive cone ${\cal COP}^6$. We proceed via a coarse intermediate classification of the possible minimal zero support set of an exceptional extremal matrix $A \in {\cal COP}^6$. To each such minimal zero support set we construct a stratified semi-algebraic manifold in … Read more
Second-order local optimality conditions involving copositivity of the Hessian of the Lagrangian on the reduced linearization cone have the advantage that there is only a small gap between sufficient (the Hessian is strictly copositive) and necessary (the Hessian is copositive) conditions. In this respect, this is a proper generalization of convexity of the Lagrangian. We … Read more
Let $A$ be an element of the copositive cone $\mathcal{COP}^n$. A zero $\mathbf{u}$ of $A$ is a nonnegative vector whose elements sum up to one and such that $\mathbf{u}^TA\mathbf{u} = 0$. The support of $\mathbf{u}$ is the index set $\mathrm{supp}\mathbf{u} \subset \{1,\dots,n\}$ corresponding to the nonzero entries of $\mathbf{u}$. A zero $\mathbf{u}$ of $A$ is … Read more
We study non-convex quadratic minimization problems under (possibly non-convex) quadratic and linear constraints, and characterize both Lagrangian and Semi-Lagrangian dual bounds in terms of conic optimization. While the Lagrangian dual is equivalent to the SDP relaxation (which has been known for quite a while, although the presented form, incorporating explicitly linear constraints, seems to be … Read more
We study the {\em Celis-Dennis-Tapia (CDT) problem}: minimize a non-convex quadratic function over the intersection of two ellipsoids. In contrast to the well-studied trust region problem where the feasible set is just one ellipsoid, the CDT problem is not yet fully understood. Our main objective in this paper is to narrow the difficulty gap that … Read more
The convex cone of $n \times n$ completely positive (CPP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CPP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for $n \le 4$ only, every DNN matrix is CPP. … Read more