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.     

Inequalities for Hardy-type operators on the cone of decreasing functions in a weighted Orlicz space

Modular inequalities and inequalities for the norms of Hardy-type operators on the cone Ω of positive functions and on the cone of positive decreasing functions with common weight and common Young function in a weighted Orlicz space are considered. A reduction theorem for the norm of the Hardy operator on the cone Ω is obtained. It is shown that this norm is equivalent to the norm of a modified operator on the cone of all positive functions in the space under consideration. It is proved that the modified operator is a generalized Hardy-type operator. The equivalence of modular inequalities on the cone Ω and modified modular inequalities on the cone of all positive functions in the Orlicz space is shown. A criterion for the validity of such inequalities in general Orlicz spaces is obtained and refined for weighted Lebesgue spaces.     

向量优化问题有效解的稳定性

运用标量化的方法,通过锥正定真有效解的上半连续性讨论了无限维赋范空间中锥有效解的部分上半连续性,证明了锥有效解的通有稳定性.在此基础上,进一步证明,在Baire纲的意义下,绝大多数的向量优化问题至少存在一个锥正定真有效解是本质的有效解,换句话说,绝大多数的向量优化问题锥有效解是几乎下半连续的.     

Factor normal wedges of semi-ordered spaces

A concept of a factor normal cone in a linear topological space is introduced and basic properties of semiordered spaces possessing a positive factor normal cone are studied. The main aim of the paper is to investigate topologies of semiordered spaces whose dual positive cone in the conjugate space is factor normal.     

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.     

On cone of nonsymmetric positive semidefinite matrices

In this paper, we analyze and characterize the cone of nonsymmetric positive semidefinite matrices (NS-psd). Firstly, we study basic properties of the geometry of the NS-psd cone and show that it is a hyperbolic but not homogeneous cone. Secondly, we prove that the NS-psd cone is a maximal convex subcone of P₀-matrix cone which is not convex. But the interior of the NS-psd cone is not a maximal convex subcone of P-matrix cone. As the byproducts, some new sufficient and necessary conditions for a nonsymmetric matrix to be positive semidefinite are given. Finally, we present some properties of metric projection onto the NS-psd cone.     

Positive solutions for a class of boundary-value problem with integral boundary conditions in Banach spaces

This paper investigates the existence and multiplicity of positive solutions for a class of nonlinear boundary-value problem of second-order differential equations with integral boundary conditions in ordered Banach spaces. The arguments are based upon a specially constructed cone and the fixed point theory in a cone for strict set contraction operators. The nonexistence of a positive solution is also studied.     

Steady-state solutions of a reaction–diffusion system arising from intraguild predation and internal storage

Intraguild predation is added to a mathematical model of competition between two species for a single nutrient with internal storage in the unstirred chemostat. At first, we established the sharp a priori estimates for nonnegative solutions of the system, which assure that all of nonnegative solutions belong to a special cone. The selection of this special cone enables us to apply the topological fixed point theorems in cones to establish the existence of positive solutions. Secondly, existence for positive steady state solutions of intraguild prey and intraguild predator is established in terms of the principal eigenvalues of associated nonlinear eigenvalue problems by means of the degree theory in the special cone. It turns out that positive steady state solutions exist when the associated principal eigenvalues are both negative or both positive.     

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.     

四阶奇异边值问题两个正解的存在性

利用锥拉伸与压缩不动点定理，给出了四阶微分方程奇异边值问题C^2[0，1]和C^2-[0，1]正解的存在性．     

四阶奇异边值问题两个正解的存在性

本文利用锥压缩和锥拉伸不动点定理,给出了四阶微分方程奇异边值问题两 个C2[0,1]和C3[0,1]正解的存在性.     

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.     

Cones Admitting Strictly Positive Functionals and Scalarization of Some Vector Optimization Problems

This paper is concerned with cones admitting strictly positive functionals and scalarization methods in multiobjective optimization. Assuming that the ordering cone admits strictly positive functionals or possesses a base in normed spaces or is a supernormal cone in a Banach space, we give scalar and scalar proper representations for vector optimization problems with convex and naturally quasiconvex data.     

Extreme positive operators on minimal and almost minimal cones

Fiedler and Pták called a cone minimal if it is n-dimensional and has n+1 extremal rays. We call a cone almost minimal if it is n-dimensional and has n+2 extremal rays. Duality properties stemming from the use of Gale pairs lead to a general technique for identifying the extreme cone-preserving (positive) operators between polyhedral cones. This technique is most effective for cones with dimension not much smaller than the number of their extreme rays. In particular, the Fiedler-Pták characterization of extreme positive operators between minimal cones is extended to the following cases: (i) operators from a minimal cone to an arbitrary polyhedral cone, (ii) operators from an almost minimal cone to a minimal cone.     

Ordering groups and validity in lattice-ordered groups

An inductive characterization is given of the subsets of a group that extend to the positive cone of a right order on the group. This characterization is used to relate validity of equations in lattice-ordered groups (?-groups) to subsets of free groups that extend to the positive cone of a right order. As a consequence, new proofs are obtained of the decidability of the word problem for free ?-groups and generation of the variety of ?-groups by the ?-group of automorphisms of the real line. An inductive characterization is also given of the subsets of a group that extend to the positive cone of an order on the group. In this case, the characterization is used to relate validity of equations in varieties of representable ?-groups to subsets of relatively free groups that extend to the positive cone of an order.     

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.     

Some geometrical aspects of semidefinite linear complementarity problems

This article studies some geometrical aspects of the semidefinite linear complementarity problem (SDLCP), which can be viewed as a generalization of the well-known linear complementarity problem (LCP). SDLCP is a special case of a complementarity problem over a closed convex cone, where the cone considered is the closed convex cone of positive semidefinite matrices. It arises naturally in the unified formulation of a pair of primal-dual semidefinite programming problems. In this article, we introduce the notion of complementary cones in the semidefinite setting using the faces of the cone of positive semidefinite matrices and show that unlike complementary cones induced by an LCP, semidefinite complementary cones need not be closed. However, under R₀-property of the linear transformation, closedness of all the semidefinite complementary cones induced by L is ensured. We also introduce the notion of a principal subtransformation with respect to a face of the cone of positive semidefinite matrices and show that for a self-adjoint linear transformation, strict copositivity is equivalent to strict semimonotonicity of each principal subtransformation. Besides the above, various other solution properties of SDLCP will be interpreted and studied geometrically.     

零点不可导时锥映射的歧点与正特征元的全局结构

研究了半序Banach空间中一类非线性锥映射歧点的存在性与正特征元的全局结构.与已知文献不同的是,不要求算子在零点沿着锥Frechet可微. 作为应用,讨论了一类椭圆型偏微分方程边值问题正解的歧点与全局结构.     

Explicit left orders on free groups extending the lexicographic order on free monoids

For every finitely generated free group, we construct an explicit left order extending the lexicographic order on the free monoid generated by the positive letters. The order is defined by a left, free action on the orbit of 0 of a free group of piecewise linear homeomorphisms of the line. The membership in the positive cone is decidable in linear time in the length of the input word. The positive cone forms a context-free language closed under word reversal.     

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.