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

A note on the Talman,Van der Heyden linear complementarity algorithm

Talman and Van der Heyden have recently proposed a pivoting algorithm for linear complementarity problems which generalizes Lemke's procedure and allows arbitrary starting points. (Lemke's method starts at the origin). This note shows that the new algorithm will work on a wider class of problems than those considered by Talman and Van der Heyden.     

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.     

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

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.     

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.     

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.     

A note on a quadratic formulation for linear complementarity problems

In this note, we discuss some properties of a quadratic formulation for linear complementarity problems. Projected SOR methods proposed by Mangasarian apply to symmetric matrices only. The quadratic formulation discussed here makes it possible to use these SOR methods for solving nonsymmetric LCPs. SOR schemes based on this formulation preserve sparsity. For proper choice of a free parameter, this quadratic formulation also preserves convexity. The value of the quadratic function for the solution of original LCP is also known.     

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.     

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.     

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.     

A nonlinear equation for linear programming

We present a characterization of the normal optimal solution of the linear program given in canonical form max{c ^tx: Ax = b, x 0}. (P) We show thatx ^* is the optimal solution of (P), of minimal norm, if and only if there exists anR > 0 such that, for eachr R, we havex ^* = (rc – A^t_r)₊. Thus, we can findx ^* by solving the following equation for _r A(rc – A^t_r)₊ = b. Moreover,(1/r) _r then converges to a solution of the dual program.On leave from The University of Alberta, Edmonton, Canada. Research partially supported by the National Science and Engineering Research Council of Canada.     

A note onQ-matrices

This paper concerns three classes of matrices that are relevant to the linear complementarity problem. We prove that within the class ofP ₀-matrices, theQ-matrices are precisely the regular matrices.Research supported by Department of Energy, Contract EY-76-S-03-0326 PA # 18.     

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.     

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.     

A note on solvability of a class of linear complementarity problems

We give a characterization of unique solvability of an infinite family of linear complementarity problems of a special form by means of a finite subset of this family.     

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.