Solution analysis for the pseudomonotone second-order cone linear complementarity problem

In this paper, we are concerned with the set of the solutions and the geometric property of the pseudomonotone second-order cone linear complementarity problems (SOCLCP). Based on Tao’s recent work [Tao, J. Optim. Theory Appl., 159, 41–56 (2013)] on pseudomonotone LCP on Euclidean Jordan algebras, we characterize the set of solutions and also derive intrinsic properties that reveal the underlying geometry of the pseudomonotone SOCLCP.     

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.     

NP-Completeness of the linear complementarity problem

We consider the linear complementarity problem (q, M) for which the data are the integer column vectorq εR ⁿ and the integer square matrixM of ordern. GLCP is the decision problem: Does (q, M) have a solution? We show that GLCP is NP-complete in the strong sense.     

On the extended linear complementarity problem

For the extended linear complementarity problem (Mangasarian and Pang, 1995), we introduce and characterize column-sufficiency, row-sufficiency andP-properties. These properties are then specialized to the vertical, horizontal and mixed linear complementarity problems. This paper is dedicated to Professor Olvi L. Mangasarian on the occasion of his 60th birthday.     

Matrices and the linear complementarity problem

The paper is a collection of results on the linear complementarity problem (q, M). The results are stated in terms of the matrix M.     

The extended linear complementarity problem

In this paper we define the Extended Linear Complementarity Problem (ELCP), an extension of the well-known Linear Complementarity Problem (LCP). We show that the ELCP can be viewed as a kind of unifying framework for the LCP and its various generalizations. We study the general solution set of an ELCP and we develop an algorithm to find all its solutions. We also show that the general ELCP is an NP-hard problem.This paper presents research results of the Belgian programme on interuniversity attraction poles (IUAP-50) initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture. The scientific responsibility is assumed by its authors.Supported by the N.F.W.O. (Belgian National Fund for Scientific Research).     

Backward errors of the linear complementarity problem

Numerical Algorithms - In this paper, we define a backward error for the linear complementarity problem (LCP), and then present an expression of it which can be employed to examine the stability of...     

Perturbation results for the linear complementarity problem

This paper presents several results concerning the perturbation of the solution vector to an linear complementarity LCP(q,M) as a function of changes in the input data (q,M).     

Solution structures of tensor complementarity problem

We introduce two new types of tensors called the strictly semimonotone tensor and the range column sufficient tensor and explore their structure properties. Based on the obtained results, we make a characterization to the solution of tensor complementarity problem.     

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 perturbation bounds of the linear complementarity problem

In this paper, new perturbation bounds for linear complementarity problems are presented based on the sign patterns of the solution of the equivalent modulus equations. The new bounds are shown to be the generalization of the existing ones.     

Total dual integrality of the linear complementarity problem

Annals of Operations Research - In this paper, we introduce total dual integrality of the linear complementarity problem (LCP) by analogy with the linear programming problem. The main idea of...     

Monotone solutions of the parametric linear complementarity problem

The parametric linear complementarity problem under study here is given by the conditionsq + αp + Mz ≥ 0,α ≥ 0,z ≥ 0,z ^T (q + αp + Mz) = 0 whereq is nonnegative. This paper answers three questions including the following one raised by G. Maier: What are the necessary and sufficient conditions onM guaranteeing that for every nonnegative starting pointq and every directionp the components of the solution to the parametric linear complementarity problem are nondecreasing functions of the parameterα?     

On cone orderings and the linear complementarity problem

This paper first generalizes a characterization of polyhedral sets having least elements, which is obtained by Cottle and Veinott [6], to the situation in which Euclidean space is partially ordered by some general cone ordering (rather than the usual ordering). We then use this generalization to establish the following characterization of the class $\text{C}$ of matrices ($\text{C}$ arises as a generalization of the class of Z-matrices; see [4], [13], [14]): M∈$\text{C}$ if and only if for every vector q for which the linear complementarity problem (q,M) is feasible, the problem (q,M) has a solution which is the least element of the feasible set of (q,M) with respect to a cone ordering induced by some simplicial cone. This latter result generalizes the characterizations of K-and Z-matrices obtained by Cottle and Veinott [6] and Tamir [21], respectively.     

A neural network for the linear complementarity problem

An artificial neural network is proposed in this paper for solving the linear complementarity problem. The new neural network is based on a reformulation of the linear complementarity problem into the unconstrained minimization problem. Our new neural network can be easily implemented on a circuit. On the theoretical aspect, we analyze the existence of the equilibrium points for our neural network. In addition, we prove that if the equilibrium point exists for the neural network, then any such equilibrium point is both asymptotically and bounded (Lagrange) stable for any initial state. Furthermore, linear programming and certain quadratical programming problems (not necessarily convex) can be also solved by the neural network. Simulation results on several problems including a nonconvex one are also reported.     

On the numerical solution of the linear complementarity problem

The well-known linear complementarity problem with definite matrices is considered. It is proposed to solve it using a global optimization algorithm in which one of the basic stages is a special local search. The proposed global search algorithm is tested using a variety of randomly generated problems; a detailed analysis of the computational experiment is given.     

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.     

Extensions of Lemke's algorithm for the linear complementarity problem

Lemke's algorithm for the linear complementarity problem fails when a desired pivot is not blocked. A projective transformation overcomes this difficulty. The transformation is performed computationally by adjoining a new row to a schema of the problem and pivoting on the element in this row and the unit constant column. Two new algorithms result; some conditions for their success are discussed.This research was partially supported by National Science Foundation, Grant GK-42092.