A fixed-point representation of the generalized complementarity problem

Eaves and Kojima have separately provided fixed-point representations of the standard complementarity problem. Although the mappings used to describe their representations appear to be different, this paper shows they are essentially the same, a unification that is accomplished via a geometric programming argument in the context of a more general complementarity problem.The authors are indebted to Professor R. Saigal of Northwestern University for helpful discussions concerning this paper.This research was partially supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under Grant No. AFOSR-77-3134.     

The eigenvalue complementarity problem

In this paper an eigenvalue complementarity problem (EiCP) is studied, which finds its origins in the solution of a contact problem in mechanics. The EiCP is shown to be equivalent to a Nonlinear Complementarity Problem, a Mathematical Programming Problem with Complementarity Constraints and a Global Optimization Problem. A finite Reformulation–Linearization Technique (Rlt)-based tree search algorithm is introduced for processing the EiCP via the lattermost of these formulations. Computational experience is included to highlight the efficacy of the above formulations and corresponding techniques for the solution of the EiCP.     

A support submatrix for the generalized linear complementarity problem

We provide an algorithm that selects, in a polynomial time, a representative submatrix whose appropriately defined LCP solution solves the GLCP. An algorithm based on support submatrices is also presented.     

The generalized linear complementarity problem revisited

Given a vertical block matrixA, we consider in this paper the generalized linear complementarity problem VLCP(q, A) introduced by Cottle and Dantzig. We formulate this problem as a linear complementarity problem with a square matrixM, a formulation which is different from a similar formulation given earlier by Lemke. Our formulation helps in extending many well-known results in linear complementarity to the generalized linear complementarity problem. We also show that the class of vertical block matrices which Cottle and Dantzig's algorithm can process is the same as the class of equivalent square matrices which Lemke's algorithm can process. We also present some degree-theoretic results on a vertical block matrix.     

On the solution and complexity of a generalized linear complementarity problem

We introduce some sufficient conditions under which a generalized linear complementarity problem (GLCP) can be solved as a pure linear complementarity problem. We also establish that the GLCP is in general a NP-Hard problem.Support of this work has been provided by the Instituto Nacional de Investigação Cientifica de Portugal (INIC) under contract 89/EXA/5.     

Kneser''s theorem and the multivalued generalized order complementarity problem

The Generalized Order Complementarity Problem studied by Isac and Kostreva is extended to multivalued mappings satisfying a condition proposed by Kneser. Existence of solutions to a related fixed point problem leads to existence theory for the new type of complementarity problem. Some important applications include problems in lubrication and in economics in which functions are set valued.     

A parametric linear complementarity problem involving derivatives

The problem considered in this paper is given by the conditions:w = q + tp + Mz, w 0, 0,w ^T = 0, where a dot denotes the derivative with respect to the scalar parametert 0. In this problem,q, p aren-vectors withq 0 andM is an byn P-matrix. This problem arises in a certain basic problem in the field of structural mechanics. The main result in this paper is the existence and uniqueness theorem of a solution to this problem. The existence proof is constructive providing a computational method of obtaining the solution asymptotically.This research is in part supported by the National Science Foundation under Grant No. ENG77-11136.     

A note on the complementarity problem

We show by an example that, in a complementarity problem where the given map is continuous and monotone on the nonnegative orthant, the existence of a feasible solution is not sufficient to guarantee existence of a solution to the complementarity problem.The author thanks Professor S. Karamardian and Dr. J. More for helpful discussions regarding this note.     

Gauss-Newton methods for the complementarity problem

Mangasarian has shown that the solution of the complementarity problem is equivalent to the solution of a system of nonlinear equations. In this paper, we propose a damped Gauss-Newton algorithm to solve this system, prove that under appropriate hypotheses one gets rapid local convergence, and present computational experience.The author would like to thank Professor Michael Ferris for pointing out a flaw in one of the proofs in an earlier preprint of this paper (Ref. 1). He is grateful to Professor Olvi Mangasarian for bringing to his attention additional references relevant to the material in this paper, and for his suggestions which resulted in a greatly improved presentation.     

序Banach空间中集值混合单调映象的耦合不动点定理

在序Banach空间中,研究了一类集值混合单调映象,用不同方法证明了两个新的耦合不动点存在性定理,所做工作扩充了文[5]的研究成果.     

A note on an open problem in linear complementarity

LetK be the class ofn × n matricesM such that for everyn-vectorq for which the linear complementarity problem (q, M) is feasible, then the problem (q, M) has a solution. Recently, a characterization ofK has been obtained by Mangasarian [5] in his study of solving linear complementarity problems as linear programs. This note proves a result which improves on such a characterization.Research sponsored by the United States Army under Contract No. DAAG29-75-C-0024 and the National Science Foundation under Grant No. MCS75-17385.     

A variable dimension algorithm for the linear complementarity problem

A variable dimension algorithm is presented for the linear complementarity problems – Mz = q; s,z 0; s _i z _i = 0 fori = 1,2, ,n. The algorithm solves a sequence of subproblems of different dimensions, the sequence being possibly nonmonotonic in the dimension of the subproblem solved. Every subproblem is the linear complementarity problem defined by a leading principal minor of the matrixM. Index-theoretic arguments characterize the points at which nonmonotonic behavior occurs.     

Stability of the linear complementarity problem at a solution point

In this paper we study the behavior of a solution of the linear complementarity problem when data are perturbed. We give characterizations of strong stability of the linear complementarity problem at a solution. In the case of stability we give sufficient and necessary conditions.     

Existence theory and Q-matrix characterization for the generalized linear complementarity problem: Revisited

We provide conditions under which a vertical block matrix is a Q-matrix if one or all representative sub-matrices are Q-matrices and vice versa. It is also shown, by means of counterexamples, that Eq. (3) of [A.A. Ebiefung, Existence theory and Q-matrix characterization for the generalized linear complementarity problem, Linear Algebra Appl. 223/224 (1995) 155-169] is incorrect.     

Continuous linear complementarity problem

We investigate a form of linear complementarity problem posed over a space of measures onX, where the matrix which occurs in the finite-dimensional linear complementarity problem is replaced by a continuous functionM(x, y),x,yX. We give a number of conditions which ensure the existence of solutions, and we discuss the extension of Lemke's algorithm to this problem.     

Monotone generalized variational inequalities and generalized complementarity problems

Some existence results for generalized variational inequalities and generalized complementarity problems involving quasimonotone and pseudomonotone set-valued mappings in reflexive Banach spaces are proved. In particular, some known results for nonlinear variational inequalities and complementarity problems in finite-dimensional and infinite-dimensional Hilbert spaces are generalized to quasimonotone and pseudomonotone set-valued mappings and reflexive Banach spaces. Application to a class of generalized nonlinear complementarity problems studied as mathematical models for mechanical problems is given.The research of the first author was supported by the National Natural Science Foundation of P. R. China and by the Ethel Raybould Fellowship, University of Queensland, St. Lucia, Brisbane, Australia.     

Banach空间中含间断项的非线性积分微分方程的可解性

我们获得了 Ｂａｎａｃｈ 空间中含间断项的非线性积分微分方程初值问题的最大最小解的存在性,并推广了许多已知结果．     

Stampacchia Generalized Vector Quasiequilibrium Problems and Vector Saddle Points

In this paper, Stampacchia generalized vector quasiequilibrium problem and generalized vector loose saddle points for set-valued mappings are introduced. By using the scalarization method and the fixed-point theorem, existence theorems are established.This work was supported by the National Natural Science Foundation of China and the Natural Science Foundation of Jiangxi Province, China. The author is grateful to Professor F. Giannessi and the referee for valuable comments and careful reading improving the original draft.Communicated by F. Giannessi     

A parallel algorithm for solving the linear complementarity problem

The concept of multitasking mathematical programs is discussed, and an application of multitasking to the multiple-cost-row linear programming problem is considered. Based on this, an algorithm for solving the Linear Complementarity Problem (LCP) in parallel is presented. A variety of computational results are presented using this multitasking approach on the CRAY X-MP/48. These results were obtained for randomly generated LCP's where thenxn dense matrixM has no special properties (hence, the problem is NP-hard). based on these results, an average time performance ofO(n ⁴) is observed.     

On the location of fixed points on pairs of spaces

Let f: (X, A)→(X, A) be an admissible selfmap of a pair of metrizable ANR's. A Nielsen number of the complement Ñ(f; X, A) and a Nielsen number of the boundary ñ(f; X, A) are defined. Ñ(f; X, A) is a lower bound for the number of fixed points on C1(X - A) for all maps in the homotopy class of f. It is usually possible to homotope f to a map which is fixed point free on Bd A, but maps in the homotopy class of f which have a minimal fixed point set on X must have at least ñ(f; X, A) fixed points on Bd A. It is shown that for many pairs of compact polyhedra these lower bounds are the best possible ones, as there exists a map homotopic to f with a minimal fixed point set on X which has exactly Ñ(f; X - A) fixed points on C1(X−A) and ñ(f; X, A) fixed points on Bd A. These results, which make the location of fixed points on pairs of spaces more precise, sharpen previous ones which show that the relative Nielsen number N(f; X, A) is the minimum number of fixed points on all of X for selfmaps of (X, A), as well as results which use Lefschetz fixed point theory to find sufficient conditions for the existence of one fixed point on C1(X−A).