Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme

It is co-NP-complete to decide whether a given matrix is copositive or not. In this paper, this decision problem is transformed into a quadratic programming problem, which can be approximated by solving a sequence of linear conic programming problems defined on the dual cone of the cone of nonnegative quadratic functions over the union of a collection of ellipsoids. Using linear matrix inequalities (LMI) representations, each corresponding problem in the sequence can be solved via semidefinite programming. In order to speed up the convergence of the approximation sequence and to relieve the computational effort of solving linear conic programming problems, an adaptive approximation scheme is adopted to refine the union of ellipsoids. The lower and upper bounds of the transformed quadratic programming problem are used to determine the copositivity of the given matrix.     

Algorithmic copositivity detection by simplicial partition

We present new criteria for copositivity of a matrix, i.e., conditions which ensure that the quadratic form induced by the matrix is nonnegative over the nonnegative orthant. These criteria arise from the representation of the quadratic form in barycentric coordinates with respect to the standard simplex and simplicial partitions thereof. We show that, as the partition gets finer and finer, the conditions eventually capture all strictly copositive matrices. We propose an algorithmic implementation which considers several numerical aspects. As an application, we present results on the maximum clique problem. We also briefly discuss extensions of our approach to copositivity with respect to arbitrary polyhedral cones.     

Finite criteria for conditional definiteness of quadratic forms

A real symmetric n × n matrix Q is A-conditionally positivesemidefinite, where A is a given m × n matrix, if x′Qx?0 whenever Ax?0, and is A-conditionally positive definite if strict inequality holds except when x=0. When A is the identity matrix these notions reduce to the well-studied notions of copositivity and strict copositivity respectively. This paper presents finite criteria, involving only the solution of sets of linear equations constructed from the matrices Q,A, for testing both types of conditional definiteness. These criteria generalize known facts about copositive matrices and, when Q is invertible and all row submatrices of A have maximal rank, can be very elegantly stated in terms of Schur complements of the matrix AQ^-1A′.     

A finite algorithm for solving general quadratic problems

Here we propose a global optimization method for general, i.e. indefinite quadratic problems, which consist of maximizing a non-concave quadratic function over a polyhedron inn-dimensional Euclidean space. This algorithm is shown to be finite and exact in non-degenerate situations. The key procedure uses copositivity arguments to ensure escaping from inefficient local solutions. A similar approach is used to generate an improving feasible point, if the starting point is not the global solution, irrespective of whether or not this is a local solution. Also, definiteness properties of the quadratic objective function are irrelevant for this procedure. To increase efficiency of these methods, we employ pseudoconvexity arguments. Pseudoconvexity is related to copositivity in a way which might be helpful to check this property efficiently even beyond the scope of the cases considered here.     

Role of copositivity in optimality criteria for nonconvex optimization problems

Second-order necessary and sufficient conditions for local optimality in constrained optimization problems are discussed. For global optimality, a criterion recently developed by Hiriart-Urruty and Lemarechal is thoroughly examined in the case of concave quadratic problems and reformulated into copositivity conditions.     

Perron–Frobenius property of copositive matrices, and a block copositivity criterion

Haynsworth and Hoffman proved in 1969 that the spectral radius of a symmetric copositive matrix is an eigenvalue of this matrix. This note investigates conditions which guarantee that an eigenvector corresponding to this dominant eigenvalue has no negative coordinates, i.e., whether the Perron–Frobenius property holds. Also a block copositivity criterion using the Schur complement is specified which may be helpful to reduce dimension in copositivity checks and which generalizes results proposed by Andersson et al. in 1995, and Johnson and Reams in 2005. Apparently, the latter five researchers were unaware of the more general results by the author precedingly published in 1987 and 1996, respectively.     

On monotonicity and search strategies in face-based copositivity detection algorithms

Central European Journal of Operations Research - Over the last decades, algorithms have been developed for checking copositivity of a matrix. Methods are based on several principles, such as...     

Tensor eigenvalue complementarity problems

This paper studies tensor eigenvalue complementarity problems. Basic properties of standard and complementarity tensor eigenvalues are discussed. We formulate tensor eigenvalue complementarity problems as constrained polynomial optimization. When one tensor is strictly copositive, the complementarity eigenvalues can be computed by solving polynomial optimization with normalization by strict copositivity. When no tensor is strictly copositive, we formulate the tensor eigenvalue complementarity problem equivalently as polynomial optimization by a randomization process. The complementarity eigenvalues can be computed sequentially. The formulated polynomial optimization can be solved by Lasserre’s hierarchy of semidefinite relaxations. We show that it has finite convergence for generic tensors. Numerical experiments are presented to show the efficiency of proposed methods.     

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.     

Measuring Stiffness

Many problems have been proposed for the testing and evaluation of mathematical software for the solution of the initial value problem for a system of ordinary differential equations. The stiffness of a given problem is of great significance for testing, but the concept is at best somewhat vague and the few quantitative measures of stiffness being used are of limited value. A relatively precise and quantitative way is proposed to answer the questions: How does the stiffness vary in the course of the integration of a given problem? Is a given problem A stiffer than a given problem B, and if so, by how much?     

组合的分组测试算法的近似控制标准

对于给定的一个集合,分组测试问题是通过一系列的测试去确定这个集合的一个子集. 在文中, 作者首先运用动态规划的理论与方法, 建立了一个近似控制标准, 目的是对分组测试算法的构建过程进行有效控制, 使所构建的算法达到最优. 其次, 应用该近似控制标准研究了在n个硬币集合中确定一个伪硬币的最小平均测试数的问题. 文中所涉及的近似控制问题, 给出了在一个给定集合中去确定这个集合的一个子集的最优分组测试算法, 该最优分组测试算法是在平均测试步骤最少意义下的最优分组测试算法.     

Finite-time stabilization of state dependent impulsive dynamical linear systems

The problem of finite-time stabilizing control design for state-dependent impulsive dynamical linear systems (SD-IDLS) is tackled in this paper. Such systems are characterized by continuous-time, linear, possibly time-varying, dynamics coupled with discrete-time, linear, possibly time-varying, dynamics. The continuous-time part determines the system evolution in any time interval between two consecutive resetting events, while the discrete-time part governs its instantaneous state jump whenever the system trajectory intersects a resetting set, i.e. a region of the state space assumed to be time-independent. By making use of a quadratic control Lyapunov function, the finite-time stabilization of SD-IDLS through a static output feedback control design is specifically discussed in this paper. A sufficient and constructive result is provided based on the conical hulls of the resetting set subregions and on some cone copositivity properties of the chosen control Lyapunov function. Such a result is based on the solution of a feasibility problem that involves a set of coupled Difference/Differential Linear Matrix Inequalities (D/DLMI), which is shown to be less conservative and more numerically amenable with respect to other results available in the literature. An example illustrates the effectiveness of the proposed approach.     

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.     

The P-matrix problem is co-NP-complete

Recently Rohn and Poljak proved that for interval matrices with rank-one radius matrices testing singularity is NP-complete. This paper will show that given any matrix family belonging to the class of matrix polytopes with hypercube domains and rank-one perturbation matrices, a class which contains the interval matrices, testing singularity reduces to testing whether a certain matrix is not a P-matrix. It follows from this result that the problem of testing whether a given matrix is a P-matrix is co-NP-complete.     

正态总体均值与标准差比在序约束下的广义p值检验

本文利用广义$p$\,-值和U-I检验法研究了多个正态总体均值与标准差比在简单半序和树序约束下的检验问题. 提出了广义检验变量, 得到了多个正态总体均值与标准差比在简单半序和树序约束下检验问题的广义$p$\,-值. 同时运用Monte Carlo方法给出了模拟结果.     

竞争风险混合模型的参数估计与检验

本文在独立同分布I型区间删失情形下,研究了竞争风险混合模型中当参数真值是内点时,参数极大似然估计的性质,获得了其强相合性和渐近正态性.在较为宽松的条件下,给出了竞争风险混合模型参数序关系假设检验的检验方法,同时得到了似然比检验统计量及其在零假设下的渐近分布为加权x~2分布,并给出了—个例子并进行了功效比较.     

On core membership testing for hedonic coalition formation games

We are concerned with the problem of core membership testing for hedonic coalition formation games, which is to decide whether a certain coalition structure belongs to the core of a given game. We show that this problem is co-NP complete when players’ preferences are additive.     

On minimax robust testing of composite hypotheses on Poisson process intensity

Statistical Inference for Stochastic Processes - The problem on the minimax testing of a Poisson process intensity is considered. For a given disjoint sets $${{\mathcal {S}}}_T$$ and $${{\mathcal...