Robust solutions to uncertain linear complementarity problems

In this paper,we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain,and it is only known to belong to a prescribed uncertainty set.We propose the notion of the p- robust counterpart and the p-robust solution of uncertain linear complementarity problems.We discuss uncertain linear complementarity problems with three different uncertainty sets,respectively,including an unknown-but-bounded uncertainty set,an ellipsoidal uncertainty set and an intersection-of-ellipsoids uncertainty set,and present some sufficient and necessary(or sufficient) conditions which p- robust solutions satisfy.Some special cases are investigated in this paper.     

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.     

On computer-assisted proofs for solutions of linear complementarity problems

In this paper we consider the linear complementarity problem where the components of the input data M and q are not exactly known but can be enclosed in intervals. We compare three tests to each other each of which can be used by a computer that supports interval arithmetic to give guaranteed bounds for a solution of the LCP defined by M and q.     

Existence and uniqueness of solutions for the generalized linear complementarity problem

Cottle and Dantzig (Ref. 1) showed that the generalized linear complementarity problem has a solution for anyqR ^m ifM is a vertical blockP-matrix of type (m ₁,...,m _n ). They also extended known characterizations of squareP-matrices to vertical blockP-matrices.Here we show, using a technique similar to Murty's (Ref. 2), that there exists a unique solution for anyqR ^m if and only ifM is a vertical blockP-matrix of type (m ₁,...,m _n ). To obtain this characterization, we employ a generalization of Tucker's theorem (Ref. 3) and a generalization of a theorem initially introduced by Gale and Nikaido (Ref. 4).     

Q-matrices and boundedness of solutions to linear complementarity problems

This paper is concerned with the existence and boundedness of the solutions to the linear complementarity problemw=Mz+q,w0,z0,w ^T z=0, for eachq ⁿ . It has been previously established that, ifM is copositive plus, then the solution set is nonempty and bounded for eachq ⁿ iffM is aQ-matrix. This result is shown to be valid also forL ₂-matrices,P ₀-matrices, nonnegative matrices, andZ-matrices.     

On the uniqueness of solutions to linear programs

We provide a constructive method of checking whether a linear programming problem (LPP) has a unique feasible or a unique optimal solution. Our method requires the solution of only one extra LPP such that the original problem has alternative solutions if and only if the optimal value of the new LPP is positive. If the original solution is not unique, an alternative solution is displayed. Possible applications are discussed.     

Isotone solutions of parametric linear complementarity problems

The parametric linear complementarity problem is given by the conditions:q + p + Mz 0, 0,z 0,z ^T (q + p + Mz) = 0. Under the assumption thatM is a P-matrix, Cottle proved that the solution mapz() of the above problem is montonically nondecreasing in the parameter for every nonnegativeq and everyp if and only ifM is a Minkowski matrix. This paper examines whether a similar result holds in various other settings including a nonlinear case.     

On semidefinite linear complementarity problems

Given a linear transformation L:? ⁿ →? ⁿ and a matrix Q∈? ⁿ , where ? ⁿ is the space of all symmetric real n×n matrices, we consider the semidefinite linear complementarity problem SDLCP(L,? ⁿ ₊,Q) over the cone ? ⁿ ₊ of symmetric n×n positive semidefinite matrices. For such problems, we introduce the P-property and its variants, Q- and GUS-properties. For a matrix A∈R ^n×n , we consider the linear transformation L _A :? ⁿ →? ⁿ defined by L _A (X):=AX+XA ^T and show that the P- and Q-properties for L _A are equivalent to A being positive stable, i.e., real parts of eigenvalues of A are positive. As a special case of this equivalence, we deduce a theorem of Lyapunov. Received: March 1999 / Accepted: November 1999?Published online April 20, 2000     

Numerical validation of solutions of linear complementarity problems

Summary. This paper proposes a validation method for solutions of linear complementarity problems. The validation procedure consists of two sufficient conditions that can be tested on a digital computer. If the first condition is satisfied then a given multidimensional interval centered at an approximate solution of the problem is guaranteed to contain an exact solution. If the second condition is satisfied then the multidimensional interval is guaranteed to contain no exact solution. This study is based on the mean value theorem for absolutely continuous functions and the reformulation of linear complementarity problems as nonsmooth nonlinear systems of equations. Received August 21, 1997 / Revised version July 2, 1998     

On the equivalence of linear complementarity problems

We show that the Extended Linear Complementarity Problem (ELCP) can be recast as a standard Linear Complementarity Problem (LCP) provided that the surplus variables or the feasible set of the ELCP are bounded. Since many extensions of the LCP are special cases of the ELCP, this implies that these extensions can be rewritten as an LCP as well. Our equivalence proof is constructive and leads to three possible numerical solution methods for a given ELCP: regular ELCP algorithms, mixed integer linear programming algorithms, and regular LCP algorithms.     

On degeneracy in linear complementarity problems

A method for handling degeneracy in linear complementarity problems is presented. It uses a sequential version of Lemke's algorithm [1] which, in the absence of degeneracy and in the case of copositive-plus matrices, finds an optimal solution or shows that none exists. The degeneracy phenomenon is overcome by modifying some constraining equations, without altering the feasible region of the problem.     

On the solution of NP-hard linear complementarity problems

In this paper two enumerative algorithms for the Linear Complementarity Problems (LCP) are discussed. These procedures exploit the equivalence of theLCP into a nonconvex quadratic and a bilinear programs. It is shown that these algorithms are efficient for processing NP-hardLCPs associated with reformulations of the Knapsack problem and should be recommended to solve difficultLCPs.     

On the existence and uniqueness of solutions in nonlinear complementarity theory

A complementarity problem is said to be globally uniquely solvable (GUS) if it has a unique solution, and this property will not change, even if any constant term is added to the mapping generating the problem.A characterization of the GUS property which generalizes a basic theorem in linear complementarity theory is given. Known sufficient conditions given by Cottle, Karamardian, and Moré for the nonlinear case are also shown to be generalized. In particular, several open questions concerning Cottle's condition are settled and a new proof is given for the sufficiency of this condition.A simple characterization for the two-dimensional case and a necessary condition for then-dimensional case are also given.The research described in this paper was carried out while N. Megiddo was visiting Tokyo Institute of Technology under a Fellowship of the Japan Society for the Promotion of Science.     

Errata: On semidefinite linear complementarity problems

We correct an error in the statement of Theorem 8 in [1]. Received: January 3, 2001 / Accepted: February 26, 2001?Published online May 18, 2001     

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 monotonicity in parametric linear complementarity problems

This paper generalizes the answers that were given by R.W. Cottle to questions that were originally raised by G. Maier.Essentially, we give necessary and sufficient conditions for some notions of monotonicity of solutions for the parametric linear complementarity problem. Our proofs are direct ones and not algorithmic, as Cottle's proofs are, and also cover a broader class of matrices.     

Existence of optimal solutions for general stochastic linear complementarity problems

In this paper we show the solvability of the expected residual minimization (ERM) formulation for the general stochastic linear complementarity problem (SLCP) under mild assumptions. The properties of the ERM formulation are dependent on the choice of NCP functions. We focus on the ERM formulations defined by the “min” NCP function and the penalized FB function, both of which are nonconvex programs on the nonnegative orthant.     

On local w-uniqueness of solutions to linear complementarity problem

We introduce the classes of column (row) competent matrices and prove that the local w-uniqueness of solutions to linear complementarity problem can be completely characterized by column competent matrices.