LipschitzianQ-matrices areP-matrices

In this note, we show that LipschitzianQ-matrices areP-matrices by obtaining a necessary condition on LipschitzianQ ₀-matrices. The sufficiency of this condition has also been established by the first two authors along with another coauthor (Murthy, Parthasarathy and Sriparna, 1995). This work was done while I visited ISI, Delhi Center during March–April, 1994. I want to express my sincere thanks for their kind hospitality.     

A copositive Q-matrix which is notR 0

Jeter and Pye gave an example to show that Pang's conjecture, thatL ₁ ?Q ?R ₀, is false while Seetharama Gowda showed that the conjecture is true for symmetric matrices. It is known thatL ₁-symmetric matrices are copositive matrices. Jeter and Pye as well as Seetharama Gowda raised the following question: Is it trueC ₀ ?Q ?R ₀? In this note we present an example of a copositive Q-matrix which is notR ₀. The example is based on the following elementary proposition: LetA be a square matrix of ordern. SupposeR ₁ =R ₂ whereR _i stands for theith row ofA. Further supposeA ₁₁ andA ₂₂ are Q-matrices whereA _ii stands for the principal submatrix omitting theith row andith column fromA. ThenA is a Q-matrix.     

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.     

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.     

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.     

An algorithm for the linear complementarity problem with upper and lower bounds

In this paper, we adapt the octahedral simplicial algorithm for solving systems of nonlinear equations to solve the linear complementarity problem with upper and lower bounds. The proposed algorithm generates a piecewise linear path from an arbitrarily chosen pointz ⁰ to a solution point. This path is followed by linear programming pivot steps in a system ofn linear equations, wheren is the size of the problem. The starting pointz ⁰ is left in the direction of one of the 2 ⁿ vertices of the feasible region. The ray along whichz ⁰ is left depends on the sign pattern of the function value atz ⁰. The sign pattern of the linear function and the location of the points in comparison withz ⁰ completely govern the path of the algorithm.This research is part of the VF-Program Equilibrium and Disequilibrium in Demand and Supply, approved by the Netherlands Ministry of Education, Den Haag, The Netherlands.     

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.     

The principal pivoting method revisited

The principal pivoting method (PPM) for the linear complementarity problem (LCP) is shown to be applicable to the class of LCPs involving the newly identified class of sufficient matrices.Research partially supported by the National Science Foundation grant DMS-8800589, U.S. Department of Energy grant DE-FG03-87ER25028 and Office of Naval Research grant N00014-89-J-1659.Dedicated to George B. Dantzig on the occasion of his 75th birthday.     

Robustness and nondegenerateness for linear complementarity problems

In this paper the main focus is on a stability concept for solutions of a linear complementarity problem. A solution of such a problem is robust if it is stable against slight perturbations of the data of the problem. Relations are investigated between the robustness, the nondegenerateness and the isolatedness of solutions. It turns out that an isolated nondegenerate solution is robust and also that a robust nondegenerate solution is isolated. Since the class of linear complementarity problems with only robust solutions or only nondegenerate solutions is not an open set, attention is paid to Garcia's classG _n of linear complementarity problems. The nondegenerate problems inG _n form an open set.     

A constructive characterization ofQ o-matrices with nonnegative principal minors

In [2] we characterized the class of matrices with nonnegative principla minors for which the linear-complementarity problem always has a solution. That class is contained in the one we study here. Our main result gives a finitely testable set of necessary and sufficient conditions under which a matrix with nonnegative principal minors has the property that if a corresponding linear complementarity problem is feasible then it is solvable. In short, we constructively characterize the matrix class known asQ _o ∩P _o . Research partially supported by the National Science Foundation Grant DMS-8420623 and U.S. Department of Energy Contract DE-AA03-76SF00326, PA # DE-AS03-76ER72018.     

Zum satz von ljapunov in vektorverbänden

Let K be a closed convex order-bounded set of an order-complete vector lattice and let A be a him continuous linear operator. Then the equality AK = A(ext K) is proved, where ext K is the set of all extremal points of K. It is shown that various generalizations of the Ljapunov-theorem on the range of vector-measures are special cases of this general statement.     

PARALLEL CHAOTIC MULTISPLITTING ITERATIVE METHODS FOR THE LARGE SPARSE LINEAR COMPLEMENTARITY PROBLEM

1. IntroductionWe consider the linear complementarity problem LCP(M,q): Find a z E m such thatwhere M = (mij) E boxs and q ~ (qi) 6 m are given real matriX and vector, respectively.This problem axises in various scientific computing areas such as the Nash equilibritun poillt ofa bimatrir game (e.g., Cottle and Dantzig[4] and Lelnke[12j) and the free boundary problems offluid mechedcs (e.g., Cryer[8]). There have been a lot of researches on the approximate solutionof the linear complemeat…     

EXPERIMENTAL STUDY OF THE ASYNCHRONOUS MULTISPLITTING RELAXATION METHODS FOR THE LINEAR COMPLEMENTARITY PROBLEMS

We study the numerical behaviours of the relaxed asynchronous multisplitting methods for the linear complementarity problems by solving some typical problems from practical applications on a real multiprocessor system. Numerical results show that the parallel multisplitting relaxation methods always perform much better than the corresponding sequential alternatives, and that the asynchronous multisplitting relaxation methods often outperform their corresponding synchronous counterparts. Moreover, the two-sweep relaxed multisplitting methods have better convergence properties than their corresponding one-sweep relaxed ones in the sense that they have larger convergence domains and faster convergence speeds. Hence, the asynchronous multisplitting unsymmetric relaxation iterations should be the methods of choice for solving the large sparse linear complementarity problems in the parallel computing environments.     

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.     

Solvability theory for a class of hemivariational inequalities involving copositive plus matrices applications in robotics

The study of the equilibrium of an object-robotic hand system including nonmonotone adhesive effects and nonclassical friction effects leads to new inequality methods in robotics. The aim of this paper is to describe these inequality methods and provide a corresponding suitable mathematical theory.