On the equivalence of nonlinear complementarity problems and least-element problems

Strictly pseudomonotoneZ-maps operating on Banach lattices are considered. Equivalence of complementarity problems and least-element problems is established under certain regularity and growth conditions. This extends a recent result by Riddell (1981) for strictly monotoneZ-maps to the pseudomonotone case. Some other problems equivalent to the above are discussed as well.This work was partially supported by the National Science Council under grant NSC 82-0208-M-110-023.Corresponding author.     

On the number of solutions to a class of linear complementarity problems

In this note, we consider the linear complementarity problemw = Mz + q, w 0, z 0, w ^T z = 0, when all principal minors ofM are negative. We show that for such a problem for anyq, there are either 0, 1, 2, or 3 solutions. Also, a set of sufficiency conditions for uniqueness is stated.The work of both authors is partially supported by a grant from the National Science Foundation, MCS 77-03472.     

Newton's method for linear complementarity problems

This paper presents an iterative, Newton-type method for solving a class of linear complementarity problems. This class was discovered by Mangasarian who had established that these problems can be solved as linear programs. Cottle and Pang characterized solutions of the problems in terms of least elements of certain polyhedral sets. The algorithms developed in this paper are shown to converge to the least element solutions. Some applications and computational results are also discussed.     

Locally unique solutions of quadratic programs,linear and nonlinear complementarity problems

It is shown that McCormick's second order sufficient optimality conditions are also necessary for a solution to a quadratic program to be locally unique and hence these conditions completely characterize a locally unique solution of any quadratic program. This result is then used to give characterizations of a locally unique solution to the linear complementarity problem. Sufficient conditions are also given for local uniqueness of solutions of the nonlinear complementarity problem.Research supported by National Science Foundation Grant MCS74-20584 A02.     

More with the Lemke complementarity algorithm

In the case that the matrix of a linear complementarity problem consists of the sum of a positive semi-definite matrix and a co-positive matrix a general condition is deduced implying that the Lemke algorithm will terminate with a complementarity solution. Applications are presented on bi-matrix games, convex quadratic programming and multi-period programs.Contributed to the XXIII TIMS Meeting, Athens, July 1977.     

On the number of solutions to a class of complementarity problems

In this paper we consider the problem of establishing the number of solutions to the complementarity problem. For the case when the Jacobian of the mapping has all principal minors negative, and satisfies a condition at infinity, we prove that the problem has either 0, 1, 2 or 3 solutions. We also show that when the Jacobian has all principal minors positive, and satisfies a condition at infinity, the problem has a unique solution.Sponsored by the United States Army under Contract No. DAAG29-75-C-0024. This material is based upon work supported by the National Science Foundation under Grant No. MCS77-03472 and Grant No. MCS78-09525. This work appeared as an MRC Technical Report No. 1964, University of Wisconsin, Madison, WI, June 1979.     

On the solution of some (parametric) linear complementarity problems with applications to portfolio selection,structural engineering and actuarial graduation

In this paper we discuss three applications of a class of (parametric) linear complementarity problems arising independently from such diverse areas as portfolio selection, structural engineering and actuarial graduation. After explaining how the complementarity problems emerge in these applications, we perform some analytical comparisons (based on operation counts and storage requirements) of several existing algorithms for solving this class of complementarity problems. We shall also present computational results to support the analytical comparisons. Finally, we deduce some conclusions about the general performance of these algorithms.This research is supported in part by the United States Army under Contract No. DAAG29-75-C-0024, the National Science Foundation under Grant No. MCS75-17385 and Grant ENG77-11136.     

Cycling in linear complementarity problems

A bound for the minimum length of a cycle in Lemke's Algorithm is derived. An example illustrates that this bound is sharp, and that the fewest number of variables is seven.     

Consistent aggregation of linear complementarity problems

Aggregating linear complementarity problems under a general definition of constrained consistency leads to the possibility of consistent aggregation of linear and quadratic programming models and bimatrix games. Under this formulation, consistent aggregation of dual variables is also achieved. Furthermore, the existence of multiple sets of aggregation operators is discussed and illustrated with a numerical example. Constrained consistency can also be interpreted as a disaggregation rule. This aspect of the problem may be important for implementing macro (economic) policies by means of micro (economic) agents.Giannini Foundation Paper No. 548.     

一类MPEC问题的SQP算法

本文研究带线性互补约束规划问题的 SQP算法 .该算法不要求精确计算初值 ,是针对初值非精确计算情形的新算法 ,证明了该算法的收敛性 .     

A class of continuous nonlinear complementarity problems

The concept of continuous nonlinear complementarity is defined. Basic properties and existence theorem are proven. Applications to continuous linear and nonlinear programming are presented. Kuhn-Tucker type conditions are established.This work was supported in part by the National Institute of General Medical Sciences under Training Grant No. 5-TO1-GM00913.     

Linear complementarity problems with an invariant number of solutions

This paper studies the class INS of all realn × n matricesM for which the linear complementarity problem (q, M) has exactlyk solutions—k depending only onM—for all realn-vectorsq interior to the coneK(M) of vectors for which (q, M) has any solution at all. This generalizes the results in Cottle and Stone (1983) which deal with the subclassU in INS wherek equals one.After the first two sections of this paper, which introduce the problem and background material, we move on to examine necessary conditions for a matrixM to be in INS (Section 3) and sufficient conditions under whichM will be in INS (Section 4). Section 5 deals with the possible values whichk may have. Section 6 discusses related results concerning the geometry of linear complementarity problems. Finally, Section 7 deals with some known and new matrix classes which are in INS.     

A class of nonlinear complementarity problems for multifunctions

Given a continuous mapF:R ⁿ R ⁿ and a lower semicontinuous positively homogeneous convex functionh:R ⁿ R, the nonlinear complementarity problem considered here is to findxR ₊ ⁿ andyh(x), the subdifferential ofh atx, such thatF(x)+y0 andx ^T (F(x)+y)=0. Some existence theorems for the above problem are given under certain conditions on the mapF. An application to quasidifferentiable convex programming is also shown.The authors are grateful to Professor O. L. Mangasarian and the referee for their substantive suggestions.     

Investigations of a certain class of linear complementarity problems

A certain class of linear complementarity problems that appeared in an economical study concerning self-employment is investigated. The principal findings for this class of linear complementarity problems are: (i) there is always a solution, which can be found by the Lemke algorithm; (ii) characterizations are found for solutions, some typical for all solutions, some typical for locally nonunique solutions, and some typical for locally unique solutions; (iii) a sufficient condition is found to guarantee a globally unique solution.The research reported in this paper is part of the project Economics of Political Decision Making of the University of Amsterdam. The author acknowledges the financial support obtained from the Ministry of Economic Affairs by way of the Research Institute for Small and Medium-Sized Business as well as the financial support of the Netherlands Organization for Scientific Research. He is grateful to two anonymous referees for many helpful suggestions, to F. A. A. M. Van Winden for stimulating discussions, and to J. J. M. Evers, H. Neudecker, and A. J. J. Talman for comments.     

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.     

A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems

There are many interior-point algorithms for LP (linear programming), QP (quadratic programming), and LCPs (linear complementarity problems). While the algebraic definitions of these problems are different from each other, we show that they are all of the same general form when we define the problems geometrically. We derive some basic properties related to such geometrical (monotone) LCPs and based on these properties, we propose and analyze a simple infeasible-interior-point algorithm for solving geometrical LCPs. The algorithm can solve any instance of the above classes without making any assumptions on the problem. It features global convergence, polynomial-time convergence if there is a solution that is smaller than the initial point, and quadratic convergence if there is a strictly complementary solution.This research was performed while the first author was visiting the Institute of Applied Mathematics and Statistics, Würzburg University as a Research Fellow of the Alexander von Humboldt Foundation.     

An extended Gauss–Seidel method for a class of multi-valued complementarity problems

The complementarity problem is one of the basic topics in nonlinear analysis; however, the methods for solving complementarity problems are usually developed for problems with single-valued mappings. In this paper we examine a class of complementarity problems with multi-valued mappings and propose an extension of the Gauss–Seidel algorithm for finding its solution. Its convergence is proved under off-diagonal antitonicity assumptions. Applications to Walrasian type equilibrium problems and to nonlinear input–output problems are also given. In this work, the authors were supported by Brescia University grant PRIN - 2006: “Oligopolistic models and order monotonicity properties”, the third author was also supported by the joint RFBR–NNSF grant, project No. 07-01-92101.     

A polynomial-time algorithm for a class of linear complementarity problems

Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x 0,y 0,x _i y _i = 0 (i = 1, 2,,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n ³ L) arithmetic operations by tracing the path of centers,{(x, y) S: x _i y _i = (i = 1, 2,,n) for some > 0} of the feasible regionS = {(x, y) 0:y = Mx + q}, whereL denotes the size of the input data of the problem.