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.     

Editorial Policy

Consider the parametric linear complementarity problem w=Mz+q+p, w0, z0, w ^T z=0, where p0, 0q0, and 0. We show that a necessary condition for every complementary map z() to be isotone for every nonzero q0 and every p is that M be either a P-matrix or a -matrix. The Cottle necessary and sufficient conditions for strong and uniform isotonicity for P-matrices are restated, with slight modifications, for -matrices.     

Ky Fan's N-matrices and linear complementarity problems

We consider the linear complementarity problem (LCP),w=Az + q, w0,z0,w ^T z=0, when all the off-diagonal entries ofA are nonpositive (the class of Z-matrices), all the proper principal minors ofA are positive and the determinant ofA is negative (the class of almost P-matrices). We shall call this the class of F-matrices. We show that ifA is a Z-matrix, thenA is an F-matrix if and only if LCP(q, A) has exactly two solutions for anyq0,q0, and has at most two solutions for any otherq. Research supported by AFOSR-89-0512.     

The Koteljanskii inequalities for mixed matrices

Recently, a new class of matrices, called mixed matrices, that unifies the Z-matrices and symmetric matrices has been identified. They share the property that when the leading principal minors are positive, all principal minors are positive. It is natural to ask what other properties of M-matrices and positive definite matrices are enjoyed by mixed matrices as well. Here, we show that mixed P-matrices satisfy a broad family of determinantal inequalities, the Koteljanskii inequalities, previously known for those two classes. In the process, other properties of mixed matrices are developed, and consequences of the Koteljanskii inequalities are given.     

A modified modulus method for symmetric positive‐definite linear complementarity problems

By reformulating the linear complementarity problem into a new equivalent fixed‐point equation, we deduce a modified modulus method, which is a generalization of the classical one. Convergence for this new method and the optima of the parameter involved are analyzed. Then, an inexact iteration process for this new method is presented, which adopts some kind of iterative methods for determining an approximate solution to each system of linear equations involved in the outer iteration. Global convergence for this inexact modulus method and two specific implementations for the inner iterations are discussed. Numerical results show that our new methods are more efficient than the classical one under suitable conditions. Copyright © 2008 John Wiley & Sons, Ltd.     

Modulus-Based GSTS Iteration Method for Linear Complementarity Problems

In this paper, a modulus-based generalized skew-Hermitian triangular splitting (MGSTS) iteration method is present for solving a class of linear complementarity problems with the system matrix either being an $H_+$-matrix with non-positive off-diagonal entries or a symmetric positive definite matrix. The convergence of the MGSTS iteration method is studied in detail. By choosing different parameters, a series of existing and new iterative methods are derived, including the modulus-based Jacobi (MJ) and the modulus-based Gauss-Seidel (MGS) iteration methods and so on. Experimental results are given to show the effectiveness and feasibility of the new method when it is employed for solving this class of linear complementarity problems.     

High quality preconditioning of a general symmetric positive definite matrix based on its UTU + UTR + RTU-decomposition

A new matrix decomposition of the form A = U^TU + U^TR + R^TU is proposed and investigated, where U is an upper triangular matrix (an approximation to the exact Cholesky factor U₀), and R is a strictly upper triangular error matrix (with small elements and the fill-in limited by that of U₀). For an arbitrary symmetric positive matrix A such a decomposition always exists and can be efficiently constructed; however it is not unique, and is determined by the choice of an involved truncation rule. An analysis of both spectral and K-condition numbers is given for the preconditioned matrix M = U^−T AU⁻¹ and a comparison is made with the RIC preconditioning proposed by Ajiz and Jennings. A concept of approximation order of an incomplete factorization is introduced and it is shown that RIC is the first order method, whereas the proposed method is of second order. The idea underlying the proposed method is also applicable to the analysis of CGNE-type methods for general non-singular matrices and approximate LU factorizations of non-symmetric positive definite matrices. Practical use of the preconditioning techniques developed is discussed and illustrated by an extensive set of numerical examples. Copyright © 1999 John Wiley & Sons, Ltd.     

A note on the convergence of the MSMAOR method for linear complementarity problems

Modulus‐based splitting, as well as multisplitting iteration methods, for linear complementarity problems are developed by Zhong‐Zhi Bai. In related papers (see Bai, Z.‐Z., Zhang, L.‐L.: Modulus‐Based Synchronous Multisplitting Iteration Methods for Linear Complementarity Problems. Numerical Linear Algebra with Applications 20 (2013) 425–439, and the references cited therein), the problem of convergence for two‐parameter relaxation methods (accelerated overrelaxation‐type methods) is analyzed under the assumption that one parameter is greater than the other. Here, we will show how we can avoid this assumption and, consequently, improve the convergence area. Copyright © 2013 John Wiley & Sons, Ltd.     

B-矩阵线性互补问题的误差界估计

利用严格对角占优M-矩阵的逆矩阵的无穷大范数的范围,给出了B-矩阵线性互补问题误差界新的估计式.相应数值算例表明了结果的有效性.     

An investigation of interior-point and block pivoting algorithms for large-scale symmetric monotone linear complementarity problems

In this paper we describe a computational study of block principal pivoting (BP) and interior-point predictor-corrector (PC) algorithms for the solution of large-scale linear complementarity problems (LCP) with symmetric positive definite matrices. This study shows that these algorithms are in general quite appropriate for this type of LCPs. The BP algorithm does not seem to be sensitive to bad scaling and degeneracy of the unique solution of the LCP, while these aspects have some effect on the performance of the PC algorithm. On the other hand, the BP method has not performed well in two LCPs with ill-conditioned matrices for which the PC algorithm has behaved quite well.A hybrid algorithm combining these two techniques is also introduced and seems to be the most robust procedure for the solution of large-scale LCPs with symmetric positive definite matrices.Support of this work has been provided by the Instituto de Telecomunicações.     

Solution of nonsymmetric linear complementarity problems by iterative methods

Convergence is established for iterative algorithms for the solution of the nonsymmetric linear complementarity problem of findingz such thatMz+q0,z0,z ^T(Mz+q)=0, whereM is a givenn×n real matrix, not necessarily symmeetric, andq is a givenn-vector. It is first shown that, if the spectral radius of a matrix related toM is less than one, then the iterates generated by the general algorithm converge to a solution of the linear complementarity problem. It turns out that convergence properties are quite similar to those of linear systems of equations. As specific cases, two important classes of matrices, Minkowski matrices and quasi-dominant diagonal matrices, are shown to satisfy this convergence condition.The author is grateful to Professor O. L. Mangasarian and the referees for their substantive suggestions and corrections.     

The area minimizing problem in conformal cones,I

In this paper we study the area minimizing problem in some kinds of conformal cones. This concept is a generalization of the cones in Euclidean spaces and the cylinders in product manifolds. We define a non-closed-minimal (NCM) condition for bounded domains. Under this assumption and other necessary conditions we establish the existence of bounded minimal graphs in mean convex conformal cones. Moreover those minimal graphs are the solutions to corresponding area minimizing problems. We can solve the area minimizing problem in non-mean convex translating conformal cones if these cones are contained in a larger mean convex conformal cones with the NCM assumption. We give examples to illustrate that this assumption can not be removed for our main results.     

A note on the complex semi‐definite matrix Procrustes problem

This note outlines an algorithm for solving the complex ‘matrix Procrustes problem’. This is a least‐squares approximation over the cone of positive semi‐definite Hermitian matrices, which has a number of applications in the areas of Optimization, Signal Processing and Control. The work generalizes the method of Allwright (SIAM J. Control Optim. 1988; 26 (3):537–556), who obtained a numerical solution to the real‐valued version of the problem. It is shown that, subject to an appropriate rank assumption, the complex problem can be formulated in a real setting using a matrix‐dilation technique, for which the method of Allwright is applicable. However, this transformation results in an over‐parametrization of the problem and, therefore, convergence to the optimal solution is slow. Here, an alternative algorithm is developed for solving the complex problem, which exploits fully the special structure of the dilated matrix. The advantages of the modified algorithm are demonstrated via a numerical example. Copyright © 2007 John Wiley & Sons, Ltd.     

子空间上的对称正定及对称半正定阵的左右特征值反问题

文[1][2][3]中讨论AX＝B的对称阵逆特征值问题，文[4][5][6]中讨论了半正定阵的逆特征值问题。本文讨论了空间了子空间上的对称正定及对称半正定阵的左右特征值反问题，给出了解存在的充分条件及解的表达式。     

A robust AINV‐type method for constructing sparse approximate inverse preconditioners in factored form

This paper suggests a new method, called AINV‐A, for constructing sparse approximate inverse preconditioners for positive‐definite matrices, which can be regarded as a modification of the AINV method proposed by Benzi and Túma. Numerical results on SPD test matrices coming from different applications demonstrate the robustness of the AINV‐A method and its superiority to the original AINV approach. Copyright © 2001 John Wiley & Sons, Ltd.     

A Survey of Reachability and Controllability for Positive Linear Systems

This paper is a survey of reachability and controllability results for discrete-time positive linear systems. It presents a variety of criteria in both algebraic and digraph forms for recognising these fundamental system properties with direct implications not only in dynamic optimization problems (such as those arising in inventory and production control, manpower planning, scheduling and other areas of operations research) but also in studying properties of reachable sets, in feedback control problems, and others. The paper highlights the intrinsic combinatorial structure of reachable/controllable positive linear systems and reveals the monomial components of such systems. The system matrix decomposition into monomial components is demonstrated by solving some illustrative examples.     

A characterization of positive semidefinite operators on a Hilbert space

In this paper, we show that, under certain conditions, a Hilbert space operator is positive semidefinite whenever it is positive semidefinite plus on a closed convex cone and positive semidefinite on the polar cone (with respect to the operator). This result is a generalization of a result by Han and Mangasarian on matrices.This paper was presented at the 90th Annual Meeting of the American Mathematical Society, Louisville, Kentucky, January 25–28, 1984.