Fully copositive matrices

The class of fully copositive (C ₀ ^f ) matrices introduced in [G.S.R. Murthy, T. Parthasarathy, SIAM Journal on Matrix Analysis and Applications 16 (4) (1995) 1268–1286] is a subclass of fully semimonotone matrices and contains the class of positive semidefinite matrices. It is shown that fully copositive matrices within the class ofQ ₀-matrices areP ₀-matrices. As a corollary of this main result, we establish that a bisymmetricQ ₀-matrix is positive semidefinite if, and only if, it is fully copositive. Another important result of the paper is a constructive characterization ofQ ₀-matrices within the class ofC ₀ ^f . While establishing this characterization, it will be shown that Graves's principal pivoting method of solving Linear Complementarity Problems (LCPs) with positive semidefinite matrices is also applicable toC ₀ ^f Q ₀ class. As a byproduct of this characterization, we observe that aC ₀ ^f -matrix is inQ ₀ if, and only if, it is completelyQ ₀. Also, from Aganagic and Cottle's [M. Aganagic, R.W. Cottle, Mathematical Programming 37 (1987) 223–231] result, it is observed that LCPs arising fromC ₀ ^f Q ₀ class can be processed by Lemke's algorithm. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

A note on a characterization of P-matrices

In this note we show that the characterization results for P-matrices due to K.G. Murty and A. Tamir which state that a given square matrixM of ordern is a P-matrix if and only if the linear complementarity problem (q, M) has a unique solution for allq in a specified finite subset of ⁿ depending onM are incorrect whenn > 3.Research supported by Dr. K.S. Krishnan (DAE) fellowship for research in Mathematics and Computer Science, Bombay, India.     

Contribution of copositive formulations to the graph partitioning problem

This article provides analysis of several copositive formulations of the graph partitioning problem and semidefinite relaxations based on them. We prove that the copositive formulations based on results from Burer [S. Burer, On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120 (Ser. A) (2009), pp. 479–495] and the author of the paper [J. Povh, Semidefinite approximations for quadratic programs over orthogonal matrices. J. Global Optim. 48 (2010), pp. 447–463] are equivalent and that they both imply semidefinite relaxations which are stronger than the Donath–Hoffman eigenvalue lower bound [W.E. Donath and A.J. Hoffman, Lower bounds for the partitioning of graphs. IBM J. Res. Develop. 17 (1973), pp. 420–425] and the projected semidefinite lower bound from Wolkowicz and Zhao [H. Wolkowicz and Q. Zhao, Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96–97 (1999), pp. 461–479].     

对称线性互补问题的乘性Schwarz算法

本文提出了求解对称性互补问题的乘性Schwarz算法,其中子问题用投影迭代方法求解.利用投影迭代算子的性质及投影迭代的收敛性,证明了算法产生的迭代点列的聚点为原互补问题的解,并在一定条件下,证明算法产生的迭代点列的聚点存在.     

A note on sufficient conditions forQ 0 andQ 0 ⋂P 0 matrices

In this note we settle an open problem posed by Al-Khayyal on a condition being sufficient for a matrix to belong to the class ofQ ₀-matrices. The answer is in the affirmative and we further relax the condition and obtain a sufficient condition forQ ₀-matrices. The results yield a class of matrices for which the linear complementarity problems can be solved as simple linear programs.     

On copositive approximation in some classical spaces of sequences

In this paper the author writes a simple characterization for the best copositive approximation in c; the space of convergent sequences, by elements of finite dimensional Chebyshev subspaces, and shows that it is unique.     

High-order copositive tensors and its applications

With the coming of the big data era, high-order high-dimensional structured tensors received much attentions of researchers" in recent years, and now they are developed into a new research branch in mathematics named multilinear algebra. As a special kind of structured tensor, the copositive tensor receives a special concern due to its wide applications in vacuum stability of a general scalar potential, polynomial optimization, tensor complementarity problem and tensor eigenvalue complementarity problem. In this review, we will give a simple survey on recent advances of high-order copositive tensors and its applications. Some potential research directions in the future are also listed in the paper.     

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.     

A new method for a class of linear variational inequalities

In this paper we introduce a new iterative scheme for the numerical solution of a class of linear variational inequalities. Each iteration of the method consists essentially only of a projection to a closed convex set and two matrix-vector multiplications. Both the method and the convergence proof are very simple.This work is supported by the National Natural Science Foundation of the P.R. China and NSF of Jiangsu.     

Generalized linear complementarity problems

It has been shown by Lemke that if a matrix is copositive plus on ⁿ , then feasibility of the corresponding linear complementarity problem implies solvability. In this article we show, under suitable conditions, that feasibility of ageneralized linear complementarity problem (i.e., defined over a more general closed convex cone in a real Hilbert space) implies solvability whenever the operator is copositive plus on that cone. We show that among all closed convex cones in a finite dimensional real Hilbert Space, polyhedral cones are theonly ones with the property that every copositive plus, feasible GLCP is solvable. We also prove a perturbation result for generalized linear complementarity problems.This research has been partially supported by the Air Force Office of Scientific Research under grants #AFOSR-82-0271 and #AFOSR-87-0350.     

OnQ-matrices

Recently, Jeter and Pye gave an example to show that Pang's conjecture, thatL ₁ Q , is false. We show in this article that the above conjecture is true for symmetric matrices. Specifically, we show that a symmetric copositive matrix is inQ if and only if it is strictly copositive.     

Necessary and sufficient conditions for the existence of complementary solutions and characterizations of the matrix classesQ andQ 0

We simplify a result by Mangasarian on the existence of solutions to the linear complementarity problem. The simplified condition gives a new geometric interpretation of the result. When used to characterize the matrix classesQ andQ ₀, our condition suggests a finitely checkable sufficient condition forP andP ₀.This work was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0173, and by general research development funds provided by the Georgia Institute of Technology.     

A new pivoting algorithm for the linear complementarity problem allowing for an arbitrary starting point

The linear complementarity problem is to find nonnegative vectors which are affinely related and complementary. In this paper we propose a new complementary pivoting algorithm for solving the linear complementarity problem as a more efficient alternative to the algorithms proposed by Lemke and by Talman and Van der Heyden. The algorithm can start at an arbitrary nonnegative vector and converges under the same conditions as Lemke's algorithm.This research is part of the VF-program Competition and Cooperation.     

Superfluous matrices in linear complementarity

Superfluous matrices were introduced by Howe (1983) in linear complementarity. In general, producing examples of this class is tedious (a few examples can be found in Chapter 6 of Cottle, Pang and Stone (1992)). To overcome this problem, we define a new class of matrices and establish that in superfluous matrices of any ordern 4 can easily be constructed. For every integerk, an example of a superfluous matrix of degreek is exhibited in the end.     

The Monotonicity of the Linear Complementarity Problem

The monotonicity of the linear complementarity problem (LCP) is discussed in this paper. Both the monotone property about the single element of the solution and the monotone property of the whole solution are presented. In order to illustrate the results, some corresponding numerical experiments are provided.     

On a “stability” in the linear complementarity problem

In this work we re-wrote the Linear Complementarity Problem in a formulation based on unknown projector operators. In particular, this formulation allows the introduction of a concept of “stability” that, in a certain way, might explain the way block pivotal algorithm performs.     

On common linear copositive Lyapunov functions for pairs of stable positive linear systems

We study the common linear copositive Lyapunov functions of positive linear systems. Firstly, we present a theorem on pairs of second order positive linear systems, and give another proof of this theorem by means of properties of geometry. Based on the process of the proof, we extended the results to a finite number of second order positive linear systems. Then we extend this result to third order systems. Finally, for higher order systems, we give some results on common linear copositive Lyapunov functions.     

A Non-Interior Continuation Algorithm for the P0 or P* LCP with Strong Global and Local Convergence Properties

We propose a non-interior continuation algorithm for the solution of the linear complementarity problem (LCP) with a P₀ matrix. The proposed algorithm differentiates itself from the current continuation algorithms by combining good global convergence properties with good local convergence properties under unified conditions. Specifically, it is shown that the proposed algorithm is globally convergent under an assumption which may be satisfied even if the solution set of the LCP is unbounded. Moreover, the algorithm is globally linearly and locally superlinearly convergent under a nonsingularity assumption. If the matrix in the LCP is a P_* matrix, then the above results can be strengthened to include global linear and local quadratic convergence under a strict complementary condition without the nonsingularity assumption.