A method for solving the general parametric linear complementarity problem

This paper presents a solution method for the general (mixed integer) parametric linear complementarity problem pLCP(q(θ),M), where the matrix M has a general structure and integrality restriction can be enforced on the solution. Based on the equivalence between the linear complementarity problem and mixed integer feasibility problem, we propose a mixed integer programming formulation with an objective of finding the minimum 1-norm solution for the original linear complementarity problem. The parametric linear complementarity problem is then formulated as multiparametric mixed integer programming problem, which is solved using a multiparametric programming algorithm. The proposed method is illustrated through a number of examples.     

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 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.     

Global Linear and Quadratic One-step Smoothing Newton Method for P 0-LCP

We propose a new smoothing Newton method for solving the P ₀-matrix linear complementarity problem (P ₀-LCP) based on CHKS smoothing function. Our algorithm solves only one linear system of equations and performs only one line search per iteration. It is shown to converge to a P ₀-LCP solution globally linearly and locally quadratically without the strict complementarity assumption at the solution. To the best of author's knowledge, this is the first one-step smoothing Newton method to possess both global linear and local quadratic convergence. Preliminary numerical results indicate that the proposed algorithm is promising.     

Even more with the Lemke complementarity algorithm

This note presents a new termination result for the Lemke linear complementarity algorithm that unifies two previous results. Special cases include linear complementarity problems satisfying the Evers condition, and those whoseM matrix is copositive-plus.This research was partially supported by NSF Grant ECS-8312008.     

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.     

An infeasible-interior-point predictor-corrector algorithm for theP *-geometric LCP

AP _*-geometric linear complementarity problem (P _*GP) as a generalization of the monotone geometric linear complementarity problem is introduced. In particular, it contains the monotone standard linear complementarity problem and the horizontal linear complementarity problem. Linear and quadratic programming problems can be expressed in a “natural” way (i.e., without any change of variables) asP _*GP. It is shown that the algorithm of Mizunoet al. [6] can be extended to solve theP _*GP. The extended algorithm is globally convergent and its computational complexity depends on the quality of the starting points. The algorithm is quadratically convergent for problems having a strictly complementary solution. The work of F. A. Potra was supported in part by NSF Grant DMS 9305760     

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.     

Modulus‐based matrix splitting iteration methods for linear complementarity problems

For the large sparse linear complementarity problems, by reformulating them as implicit fixed‐point equations based on splittings of the system matrices, we establish a class of modulus‐based matrix splitting iteration methods and prove their convergence when the system matrices are positive‐definite matrices and H₊‐matrices. These results naturally present convergence conditions for the symmetric positive‐definite matrices and the M‐matrices. Numerical results show that the modulus‐based relaxation methods are superior to the projected relaxation methods as well as the modified modulus method in computing efficiency. Copyright © 2009 John Wiley & Sons, Ltd.     

Growth behavior of a class of merit functions for the nonlinear complementarity problem

When the nonlinear complementarity problem is reformulated as that of finding the zero of a self-mapping, the norm of the selfmapping serves naturally as a merit function for the problem. We study the growth behavior of such a merit function. In particular, we show that, for the linear complementarity problem, whether the merit function is coercive is intimately related to whether the underlying matrix is aP-matrix or a nondegenerate matrix or anR _o-matrix. We also show that, for the more popular choices of the merit function, the merit function is bounded below by the norm of the natural residual raised to a positive integral power. Thus, if the norm of the natural residual has positive order of growth, then so does the merit function.This work was partially supported by the National Science Foundation Grant No. CCR-93-11621.The author thanks Dr. Christian Kanzow for his many helpful comments on a preliminary version of this paper. He also thanks the referees for their helpful suggestions.     

<Emphasis FontCategory="NonProportional">L</Emphasis>-Matrices and solvability of linear complementarity problems by a linear program-Matrices and solvability of linear complementarity problems by a linear program

The classes ofL ₁-matrices,L ₂-matrices,L ₃-matrices andW-matrices are introduced to study solvability of a linear complementarity problem via solving a linear program. Three sufficient conditions are presented to guarantee that a linear complementarity problem is solvable via a linear program. The new sufficient conditions are weaker than the ones introduced by Mangasarian. This fact is also illustrated by an example. Partially supported by NSFC. This author is also with College of Business Administration of Human University as a Lotus chair professor.     

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 critical index algorithm for nearest point problems on simplicial cones

We consider the linear complementarity problem (q, M) in whichM is a positive definite symmetric matrix of ordern. This problem is equivalent to a nearest point problem [; b] in which = {A.₁,, A. _n } is a basis for R ⁿ ,b is a given point in R ⁿ ; and it is required to find the nearest point in the simplicial cone Pos() tob. We develop an algorithm for solving the linear complementarity problem (q, M) or the equivalent nearest point problem [; b]. Computational experience in comparison with an existing algorithm is presented.Research effort partially supported by the Air Force Office of Scientific Research. Air Force Systems Command, USAF, under grant No. AFOSR 78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes, not withstanding any copyright notation hereon.     

A continuation method for linear complementarity problems with P 0 matrix

In this article, we propose a new continuation method for solving the linear complementarity problem (LCP). The method solves one system of linear equations and carries out only a one-line search at each iteration. The continuation method is based on a modified smoothing function. The existence and continuity of a smooth path for solving the LCP with a P ₀ matrix are discussed. We investigate the boundedness of the iteration sequence generated by our continuation method under the assumption that the solution set of the LCP is nonempty and bounded. It is shown to converge to an LCP solution globally linearly and locally superlinearly without the assumption of strict complementarity at the solution under suitable assumption. In addition, some numerical results are also reported in this article.     

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.     

Two-step modulus-based matrix splitting iteration method for linear complementarity problems

Bai has recently presented a modulus-based matrix splitting iteration method, which is a powerful alternative for solving the large sparse linear complementarity problems. In this paper, we further present a two-step modulus-based matrix splitting iteration method, which consists of a forward and a backward sweep. Its convergence theory is proved when the system matrix is an H ₊-matrix. Moreover, for the two-step modulus-based relaxation iteration methods, more exact convergence domains are obtained without restriction on the Jacobi matrix associated with the system matrix, which improve the existing convergence theory. Numerical results show that the two-step modulus-based relaxation iteration methods are superior to the modulus-based relaxation iteration methods for solving the large sparse linear complementarity problems.     

A new non-interior continuation method for <Emphasis Type="Italic">P</Emphasis><Subscript>0</Subscript>-NCP based on a SSPM-function

In this paper, we consider a new non-interior continuation method for the solution of nonlinear complementarity problem with P ₀-function (P ₀-NCP). The proposed algorithm is based on a smoothing symmetric perturbed minimum function (SSPM-function), and one only needs to solve one system of linear equations and to perform only one Armijo-type line search at each iteration. The method is proved to possess global and local convergence under weaker conditions. Preliminary numerical results indicate that the algorithm is effective.     

Existence theory for generalized nonlinear complementarity problems

The nonlinear complementarity problem is generalized by replacing the usual nonnegative ordering ofR ⁿ by an ordering generated by a convex cone. Two new classes of operators are introduced, each of which is used to guarantee the existence of a solution to the generalized problem. The new classes can be seen to be broader than previously studied classes. In addition, conditions are presented under which the solution set of the generalized linear complementarity problem is shown to have at most a finite number of solutions.This research was partially supported by National Science Foundation, Grant No. GP-16293, and constitutes part of the junior author's doctoral thesis. The authors are indebted to Dr. Carlton E. Lemke for many helpful discussions.     

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.