On the algebraic structure of the copositive cone
- PDF / 407,139 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 99 Downloads / 167 Views
On the algebraic structure of the copositive cone Roland Hildebrand1 Received: 18 January 2020 / Accepted: 13 May 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract We decompose the copositive cone COP n into a disjoint union of a finite number of open subsets SE of algebraic sets Z E . Each set SE consists of interiors of faces of COP n . On each irreducible component of Z E these faces generically have the same dimension. Each algebraic set Z E is characterized by a finite collection E = {(Iα , Jα )}α=1,...,|E | of pairs of index sets. Namely, Z E is the set of symmetric matrices A such that the submatrices A Jα ×Iα are rank-deficient for all α. For every copositive matrix A ∈ SE , the index sets Iα are the minimal zero supports of A. If u α is a corresponding minimal zero, then Jα is the set of indices j such that (Au α ) j = 0. We call the pair (Iα , Jα ) the extended support of the zero u α , and E the extended minimal zero support set of A. We provide some necessary conditions on E for SE to be non-empty, and for a subset SE to intersect the boundary of another subset SE . Keywords Copositive cone · Minimal zero · Facial structure · Algebraic sets
1 Introduction An element A of the space S n of real symmetric n × n matrices is called copositive if x T Ax ≥ 0 for all vectors x ∈ Rn+ . The set of such matrices forms the copositive cone COP n . This cone plays an important role in non-convex optimization, as many difficult optimization problems can be reformulated as conic programs over COP n . For a detailed survey of the applications of this cone see, e.g., [3,4,10,13]. In [8] the local structure of the cone COP n around a given copositive matrix A was considered. In particular, the cone of feasible directions and the tangent cone at A and the minimal face of A have been computed. These objects have a description in terms of the minimal zeros of A. A zero u of a copositive matrix A is a non-zero nonnegative vector such that u T Au = 0 [1,6]. The support supp u of a zero u = (u 1 , . . . , u n )T ∈ Rn+ is the subset of indices
B 1
Roland Hildebrand [email protected] CNRS, Grenoble INP, LJK, Univ. Grenoble Alpes, 38000 Grenoble, France
123
R. Hildebrand
j ∈ {1, . . . , n} such that u j > 0. A zero u of A is called minimal if there is no zero v of A such that supp v ⊂ supp u holds strictly [11]. The minimal zero support set, A of minimal zero supports of a copositive matrix A is a i.e., the ensemble supp Vmin characteristic that yields a finite classification of the matrices in COP n . However, this classification is quite coarse, e.g., the set of matrices A ∈ COP n which share the minimal zero support set with A may have a description by different ensembles of equalities and inequalities around different points. Here we make a further step in the study of the local properties of COP n . While the paper [8] focussed on the infinitesimal structure of COP n near a given matrix A, in this work we consider finite neighbourhoods of A. To this end we propose a f
Data Loading...
