Optimization Online


Considering Copositivity Locally

Peter J.C. Dickinson (p.j.c.dickinson***at***utwente.nl)
Roland Hildebrand (Roland.Hildebrand***at***imag.fr)

Abstract: 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 called minimal if there does not exist another zero $\mathbf{v}$ of $A$ such that its support $\mathrm{supp}\mathbf{v}$ is a strict subset of $\mathrm{supp}\mathbf{u}$. Our main result is a characterization of the cone of feasible directions at $A$, i.e., the convex cone $\mathcal{K}^A$ of real symmetric $n \times n$ matrices $B$ such that there exists $\delta > 0$ satisfying $A + \delta B \in \mathcal{COP}^n$. This cone is described by a set of linear inequalities on the elements of $B$ constructed from the set of zeros of $A$ and their supports. This characterization furnishes descriptions of the minimal face of $A$ in $\mathcal{COP}^n$, and of the minimal exposed face of $A$ in $\mathcal{COP}^n$, by sets of linear equalities and inequalities constructed from the set of minimal zeros of $A$ and their supports. In particular, we can check whether $A$ lies on an extreme ray of $\mathcal{COP}^n$ by examining the solution set of a system of linear equations. In addition, we deduce a simple necessary and sufficient condition on the irreducibility of $A$ with respect to a copositive matrix $C$. Here $A$ is called irreducible with respect to $C$ if for all $\delta > 0$ we have $A - \delta C \not\in \mathcal{COP}^n$.

Keywords: copositive matrix, face, irreducibility, extreme rays

Category 1: Linear, Cone and Semidefinite Programming (Other )

Citation: Submitted

Download: [PDF]

Entry Submitted: 04/14/2014
Entry Accepted: 04/14/2014
Entry Last Modified: 02/01/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society