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.     

An improved algorithm to test copositivity

Copositivity plays a role in combinatorial and nonconvex quadratic optimization. However, testing copositivity of a given matrix is a co-NP-complete problem. We improve a previously given branch-and-bound type algorithm for testing copositivity and discuss its behavior in particular for the maximum clique problem. Numerical experiments indicate that the speedup is considerable.     

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.     

On condition numbers of polynomial eigenvalue problems

In this paper, we investigate condition numbers of eigenvalue problems of matrix polynomials with nonsingular leading coefficients, generalizing classical results of matrix perturbation theory. We provide a relation between the condition numbers of eigenvalues and the pseudospectral growth rate. We obtain that if a simple eigenvalue of a matrix polynomial is ill-conditioned in some respects, then it is close to be multiple, and we construct an upper bound for this distance (measured in the euclidean norm). We also derive a new expression for the condition number of a simple eigenvalue, which does not involve eigenvectors. Moreover, an Elsner-like perturbation bound for matrix polynomials is presented.     

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.     

A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W‐tensors, which not only extends the well‐studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory. We then show that finding the maximum H‐eigenvalue of an even‐order symmetric W‐tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing the maximum H‐eigenvalue of W‐tensors and is based on a new structured sums‐of‐squares decomposition result for a nonnegative polynomial induced by W‐tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H‐eigenvalue of W‐tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H‐eigenvalues of large‐size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state‐of‐the‐art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z‐tensors, whose order may be even or odd.     

An extremal property of the eigenvalue of irreducible matrices in idempotent algebra and solution of the Rawls location problem

An extremal property of the eigenvalue of an irreducible matrix in idempotent algebra is studied. It is shown that this value is the minimum value of some functional defined using this matrix on the set of vectors with nonzero components. The minimax problem of location of a single facility (the Rawls problem) on a plane with rectilinear distance is considered. For this problem, we give the corresponding representation in terms of idempotent algebra and suggest a new algebraic solution, which is based on the results of investigation of the extremal property of eigenvalue and reduces to finding the eigenvalue and eigenvectors of a certain matrix.     

Eigenvalue Multiplicity Estimate in Semidefinite Programming

A semidefinite programming problem is a mathematical program in which the objective function is linear in the unknowns and the constraint set is defined by a linear matrix inequality. This problem is nonlinear, nondifferentiable, but convex. It covers several standard problems (such as linear and quadratic programming) and has many applications in engineering. Typically, the optimal eigenvalue multiplicity associated with a linear matrix inequality is larger than one. Algorithms based on prior knowledge of the optimal eigenvalue multiplicity for solving the underlying problem have been shown to be efficient. In this paper, we propose a scheme to estimate the optimal eigenvalue multiplicity from points close to the solution. With some mild assumptions, it is shown that there exists an open neighborhood around the minimizer so that our scheme applied to any point in the neighborhood will always give the correct optimal eigenvalue multiplicity. We then show how to incorporate this result into a generalization of an existing local method for solving the semidefinite programming problem. Finally, a numerical example is included to illustrate the results.     

Perron–Frobenius theorem for hypermatrices in the max algebra

Recently, there have been many intriguing new developments in the study of hypermatrices and their associated eigenvalue problems. In particular, results coming from the matrix setting when studying the max algebra have shown especially attractive combinatorial features. We now extend this max algebra setting into the realm of hypermatrices. Considering that the max algebra has shown particular significance in optimization problems for the matrix setting, we look to examine and extend these results in the higher order conditions. Furthermore, we establish some algebraic properties for hypermatrices and then proceed to extend the Perron–Frobenius Theorem for this setting and prove the existence of a unique eigenvalue. We continue by stating a result from Nussbaum, that the Min–Max theorem holds, and provide a proof for completeness. For strongly increasing hypermatrices, an iterative algorithm which converges to our unique eigenvalue is given. Finally, we conclude with an analysis of our results in the hypergraph setting.     

Oja神经网络模型的有限逸时性

O ja连续型全反馈神经网络模型可以有效计算实对称矩阵的主特征向量,该网络的动态行为由描述其模型的微分方程所决定,详细研究了O ja动力系统的稳定性问题.对于非正定实对称矩阵最大特征根为零,且至少有一特征根为负的情形,证明了从单位球外出发的解并不一定必然导致有限逸时,完善了O ja模型计算实对称矩阵主特征向量的收敛性结果,数值实验结果进一步验证了理论分析的正确性.     

Structured eigenvalue condition numbers and linearizations for matrix polynomials

This work is concerned with eigenvalue problems for structured matrix polynomials, including complex symmetric, Hermitian, even, odd, palindromic, and anti-palindromic matrix polynomials. Most numerical approaches to solving such eigenvalue problems proceed by linearizing the matrix polynomial into a matrix pencil of larger size. Recently, linearizations have been classified for which the pencil reflects the structure of the original polynomial. A question of practical importance is whether this process of linearization significantly increases the eigenvalue sensitivity with respect to structured perturbations. For all structures under consideration, we show that this cannot happen if the matrix polynomial is well scaled: there is always a structured linearization for which the structured eigenvalue condition number does not differ much. This implies, for example, that a structure-preserving algorithm applied to the linearization fully benefits from a potentially low structured eigenvalue condition number of the original matrix polynomial.     

Normal equivalent to an arbitrary diagonalizable matrix

The aim of this paper is to reduce the eigenvalue problem of a diagonalizable matrix to the eigenvalue problem of an equivalent normal matrix. We use for this purpose a minimization strategy, which is also applicable for transforming an arbitrary nondiagonalizable matrix to an almost normal one.     

用改进遗传算法求解矩阵实特征值

依据矩阵特征值的分布理论,通过确定矩阵实特征值的分布区域,用实数编码和具有自适应交叉概率和变异概率的遗传算法来求解矩阵实特征值的近似值.仿真结果表明,此算法可以达到一定的精度,具有一定的通用性.并给求矩阵特征值提供了一种快速的方法.     

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.     

Hermitian matrix polynomials with real eigenvalues of definite type. Part I: Classification

The spectral properties of Hermitian matrix polynomials with real eigenvalues have been extensively studied, through classes such as the definite or definitizable pencils, definite, hyperbolic, or quasihyperbolic matrix polynomials, and overdamped or gyroscopically stabilized quadratics. We give a unified treatment of these and related classes that uses the eigenvalue type (or sign characteristic) as a common thread. Equivalent conditions are given for each class in a consistent format. We show that these classes form a hierarchy, all of which are contained in the new class of quasidefinite matrix polynomials. As well as collecting and unifying existing results, we make several new contributions. We propose a new characterization of hyperbolicity in terms of the distribution of the eigenvalue types on the real line. By analyzing their effect on eigenvalue type, we show that homogeneous rotations allow results for matrix polynomials with nonsingular or definite leading coefficient to be translated into results with no such requirement on the leading coefficient, which is important for treating definite and quasidefinite polynomials. We also give a sufficient and necessary condition for a quasihyperbolic matrix polynomial to be strictly isospectral to a real diagonal quasihyperbolic matrix polynomial of the same degree, and show that this condition is always satisfied in the quadratic case and for any hyperbolic matrix polynomial, thereby identifying an important new class of diagonalizable matrix polynomials.     

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...     

On graphs with exactly one anti-adjacency eigenvalue and beyond

The anti-adjacency matrix of a graph is constructed from the distance matrix of a graph by keeping each row and each column only the largest distances. This matrix can be interpreted as the opposite of the adjacency matrix, which is instead constructed from the distance matrix of a graph by keeping in each row and each column only the distances equal to 1. The (anti-)adjacency eigenvalues of a graph are those of its (anti-)adjacency matrix. Employing a novel technique introduced by Haemers (2019) [9], we characterize all connected graphs with exactly one positive anti-adjacency eigenvalue, which is an analog of Smith's classical result that a connected graph has exactly one positive adjacency eigenvalue iff it is a complete multipartite graph. On this basis, we identify the connected graphs with all but at most two anti-adjacency eigenvalues equal to ?2 and 0. Moreover, for the anti-adjacency matrix we determine the HL-index of graphs with exactly one positive anti-adjacency eigenvalue, where the HL-index measures how large in absolute value may be the median eigenvalues of a graph. We finally propose some problems for further study.     

Perturbation theory of selfadjoint matrices and sign characteristics under generic structured rank one perturbations

For selfadjoint matrices in an indefinite inner product, possible canonical forms are identified that arise when the matrix is subjected to a selfadjoint generic rank one perturbation. Genericity is understood in the sense of algebraic geometry. Special attention is paid to the perturbation behavior of the sign characteristic. Typically, under such a perturbation, for every given eigenvalue, the largest Jordan block of the eigenvalue is destroyed and (in case the eigenvalue is real) all other Jordan blocks keep their sign characteristic. The new eigenvalues, i.e. those eigenvalues of the perturbed matrix that are not eigenvalues of the original matrix, are typically simple, and in some cases information is provided about their sign characteristic (if the new eigenvalue is real). The main results are proved by using the well known canonical forms of selfadjoint matrices in an indefinite inner product, a version of the Brunovsky canonical form and on general results concerning rank one perturbations obtained.     

Conditioning analysis of block incomplete factorizations and its application to elliptic equations

Summary. The paper deals with eigenvalue estimates for block incomplete factorization methods for symmetric matrices. First, some previous results on upper bounds for the maximum eigenvalue of preconditioned matrices are generalized to each eigenvalue. Second, upper bounds for the maximum eigenvalue of the preconditioned matrix are further estimated, which presents a substantial improvement of earlier results. Finally, the results are used to estimate bounds for every eigenvalue of the preconditioned matrices, in particular, for the maximum eigenvalue, when a modified block incomplete factorization is used to solve an elliptic equation with variable coefficients in two dimensions. The analysis yields a new upper bound of type for the condition number of the preconditioned matrix and shows clearly how the coefficients of the differential equation influence the positive constant . Received March 27, 1996 / Revised version received December 27, 1996     

The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

We consider the eigenvalues and eigenvectors of finite, low rank perturbations of random matrices. Specifically, we prove almost sure convergence of the extreme eigenvalues and appropriate projections of the corresponding eigenvectors of the perturbed matrix for additive and multiplicative perturbation models.The limiting non-random value is shown to depend explicitly on the limiting eigenvalue distribution of the unperturbed random matrix and the assumed perturbation model via integral transforms that correspond to very well-known objects in free probability theory that linearize non-commutative free additive and multiplicative convolution. Furthermore, we uncover a phase transition phenomenon whereby the large matrix limit of the extreme eigenvalues of the perturbed matrix differs from that of the original matrix if and only if the eigenvalues of the perturbing matrix are above a certain critical threshold. Square root decay of the eigenvalue density at the edge is sufficient to ensure that this threshold is finite. This critical threshold is intimately related to the same aforementioned integral transforms and our proof techniques bring this connection and the origin of the phase transition into focus. Consequently, our results extend the class of ‘spiked’ random matrix models about which such predictions (called the BBP phase transition) can be made well beyond the Wigner, Wishart and Jacobi random ensembles found in the literature. We examine the impact of this eigenvalue phase transition on the associated eigenvectors and observe an analogous phase transition in the eigenvectors. Various extensions of our results to the problem of non-extreme eigenvalues are discussed.