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.     

New approximations for the cone of copositive matrices and its dual

We provide convergent hierarchies for the convex cone $\mathcal{C }$ of copositive matrices and its dual $\mathcal{C }^*$ , the cone of completely positive matrices. In both cases the corresponding hierarchy consists of nested spectrahedra and provide outer (resp. inner) approximations for $\mathcal{C }$ (resp. for its dual $\mathcal{C }^*$ ), thus complementing previous inner (resp. outer) approximations for $\mathcal{C }$ (for $\mathcal{C }^*$ ). In particular, both inner and outer approximations have a very simple interpretation. Finally, extension to $\mathcal{K }$ -copositivity and $\mathcal{K }$ -complete positivity for a closed convex cone $\mathcal{K }$ , is straightforward.     

On the cone of nonnegative circuits

We discuss three equivalent formulations of a theorem of Seymour on nonnegative sums of circuits of a graph, and present a different (but not shorter) proof of Seymour's resut.Research supported, in part, by an IBM Postdoctoral Fellowship, a grant of the Alexander von Humboldt-Stiftung, and NSF grant DMS-8504050.     

On the fiber cone of monomial ideals

Archiv der Mathematik - We consider the fiber cone of monomial ideals. It is shown that for monomial ideals $$I\subset K[x,y]$$ of height 2, generated by 3 elements, the fiber cone F(I) of I is a...     

On the semiring of cone preserving maps

If K is a proper cone in Rⁿ, then the cone of all linear operators that preserve K, denoted by π(K), forms a semiring under usual operator addition and multiplication. Recently J.G. Horne examined the ideals of this semiring. He proved that if K₁, K₂ are polyhedral cones such that π(K₁) and π(K₂) are isomorphic as semirings, then K₁ and K₂ are linearly isomorphic. The study of this semiring is continued in this paper. In Sec. 3 ideals of π(K) which are also faces are characterized. In Sec. 4 it is shown that π(K) has a unique minimal two-sided ideal, namely, the dual cone of π(K¹), where K¹ is the dual cone of K. Extending Horne's result, it is also proved that the cone K is characterized by this unique minimal two-sided ideal of π(K). The set of all faces of π(K) inherits a quotient semiring structure from π(K). Properties of this face-semiring are given in Sec. 5. In particular, it is proved that this face-semiring admits no nontrivial congruence relation iff the duality operator of π(K) is injective. In Sec. 6 the maximal one-sided and two-sided ideals of π(K) are identified. In Sec. 8 it is shown that π(K) never satisfies the ascending-chain condition on principal one-sided ideals. Some partial results on the question of topological closedness of principal one-sided ideals of π(K) are also given.     

On the metrizability of cone metric spaces

We have shown in this paper that a (complete) cone metric space (X,E,P,d) is indeed (completely) metrizable for a suitable metric D. Moreover, given any finite number of contractions f₁,…,fn on the cone metric space (X,E,P,d), D can be defined in such a way that these functions become also contractions on (X,D).     

On the automorphism group of a cone

Let V be a real finite dimensional vector space, and let C be a full cone in C. In Sec. 3 we show that the group of automorphisms of a compact convex subset of V is compact in the uniform topology, and relate the group of automorphisms of C to the group of automorphisms of a compact convex cross-section of C. This section concludes with an application which generalizes the result that a proper Lorentz transformation has an eigenvector in the light cone. In Sec. 4 we relate the automorphism group of C to that of its irreducible components. In Sec. 5 we show that every compact group of automorphisms of C leaves a compact convex cross-section invariant. This result is applied to show that if C is a full polyhedral cone, then the automorphism group of C is the semidirect product of the (finite) automorphism group of a polytopal cross-section and a vector group whose dimension is equal to the number of irreducible components of C. An example shows that no such result holds for more general cones.     

关于Smarandache对偶函数

定义Smarandache对偶函数S*(n)为最大的正整数m使得m!|n.定义另一种双阶乘函数S**(n)为最大的正整数2m-1使得(2m-1)!!|n,其中2 n;且当2|n时,为最大的正整数2m使得(2m)!!|n.本文的主要目的是利用初等方法研究一个包含S**(n)的无穷级数的收敛性,并给出一个有趣的恒等式.     

On the dual rigidity matrix

A novel characterization of bar-and-joint framework rigidity was introduced in [A.Y. Alfakih. Graph rigidity via Euclidean distance matrices. Linear Algebra Appl., 310 (2000) 149-165; A.Y. Alfakih. On rigidity and realizability of weighted graphs. Linear Algebra Appl., 325 (2001) 57-70]. This characterization uses the notion of normal cones of convex sets to define a matrix whose rank determines whether or not a given generic framework is rigid. Furthermore, this characterization was derived under the assumption that the framework of interest G(p) has an equivalent framework G(q) in R^n-1, where n is the number of vertices of G(p). In this paper we show that the matrix corresponding to a framework G(p) contains the same information as the well-known rigidity matrix R. Whereas the entries of R are a function of the positions of the vertices of G(p), the entries of are a function of the Gale matrix corresponding to G(p). Furthermore, while the number of rows of R is equal to the number of edges of G(p), the number of columns of is equal to the number of missing edges of G(p). We also show that the assumption of the existence of an equivalent framework G(q) in R^n-1 can be dropped and we give the precise relation between the left-nullspaces, and consequently the nullspaces, of R and .     

On the duality operator of a convex cone

Let C be a convex set in Rⁿ. For each y?C, the cone of C at y, denoted by cone(y, C), is the cone {α(x ? y): α ? 0 and x?C}. If K is a cone in Rⁿ, we shall denote by $\text{K}{}^1$ its dual cone and by F(K) the lattice of faces of K. Then the duality operator of K is the mapping $\text{d}{}_{\mathrm{K}}\text{: F(K) → F(K}{}^1\text{)}$ given by $\text{d}{}_{\mathrm{K}}\text{(F) = (}\text{span}\text{F)}{}^{\mathrm{\perp }}\text{∩ K}{}^1$. Properties of the duality operator d_K of a closed, pointed, full cone K have been studied before. In this paper, we study d_K for a general cone K, especially in relation to d_{cone(y, K)}, where y?K. Our main result says that, for any closed cone K in Rⁿ, the duality operator d_K is injective (surjective) if and only if the duality operator d_{cone(y, K)} is injective (surjective) for each vector y?K ～ [K ∩ (? K)]. In the last part of the paper, we obtain some partial results on the problem of constructing a compact convex set C, which contains the zero vector, such that cone (0, C) is equal to a given cone.     

On the similarity of dual operators

Let k be a field with an involution σ and a non-degenerate sesquilinear form, where V,W are n-dimensional k-spaces. Assume that ΛEnd(V) and Λ^*End(W) are dual operators. We show that if Λ and Λ^* are similar, then Λ^*=Λ^-1, where :V→W is Hermitian.     

On a cone covering problem

Given a set of polyhedral cones C₁,…,Ck⊂Rd, and a convex set D, does the union of these cones cover the set D? In this paper we consider the computational complexity of this problem for various cases such as whether the cones are defined by extreme rays or facets, and whether D is the entire Rd or a given linear subspace Rt. As a consequence, we show that it is coNP-complete to decide if the union of a given set of convex polytopes is convex, thus answering a question of Bemporad, Fukuda and Torrisi.     

On approximation of dual spaces and dual operators

We study the connection between equations which approximate an initial abstract linear equation and the adjoint one. We prove that the operator which is adjoint to the approximating one approximates the adjoint operator. As examples we consider adjoint linear integral equations and mutually dual linear programming problems.     

The dual description of a cone integer-valuedly-generated by a finite set of vectors

A discrete analog is obtained in the paper for certain classical results of the theory of linear inequalities.