General Characterization of a Linear Complementarity Problem

Youssef Elfoutayeni, Mohamed Khaladi

  Open Access OPEN ACCESS  Peer Reviewed PEER-REVIEWED

General Characterization of a Linear Complementarity Problem

Youssef Elfoutayeni1,, Mohamed Khaladi2

1Analysis, Modeling and Simulation Laboratory, University Hassan II Casablanca, Morocco

2MPD Laboratory, UCAM, Marrakech, Morocco and UMI UMMISCO, IRD - UPMC, Paris, France

Abstract

For a given matrix and a vector of, the linear complementarity problem LCP(A,b) is to find a vector in satisfying, and or showing that such a vector does not exist. Under various hypotheses on the matrix, LCP (A,b) was studied by many authors in the last decade. In previous papers we have developed algorithms for solving some classes of LCP (A,b). In this work, we give a general characterization of the solutions of LCP (A,b), we show under what conditions the problem has a solution or not and how to calculate the solution when they exist. We then apply this characterization to some examples and find the solutions or show that the problem LCP (A,b) has no solution.

At a glance: Figures

1
Prev Next

Cite this article:

  • Elfoutayeni, Youssef, and Mohamed Khaladi. "General Characterization of a Linear Complementarity Problem." American Journal of Modeling and Optimization 1.1 (2013): 1-5.
  • Elfoutayeni, Y. , & Khaladi, M. (2013). General Characterization of a Linear Complementarity Problem. American Journal of Modeling and Optimization, 1(1), 1-5.
  • Elfoutayeni, Youssef, and Mohamed Khaladi. "General Characterization of a Linear Complementarity Problem." American Journal of Modeling and Optimization 1, no. 1 (2013): 1-5.

Import into BibTeX Import into EndNote Import into RefMan Import into RefWorks

1. Introduction

For a given matrix and a given vector , the linear complementarity problem LCP(A,b) is to find a vector in satisfying

(1)

or to show that such a vector does not exist.

The constraint is known as the complementarity constraint. Since the variables are restricted to be nonnegative, this implies that for each to and hence, for any solution to at least one of the variables in the pair , should be equal to zero for to .

The problem can be equivalently stated as

(2)

The linear Complementarity Problem is abbreviated as or .

This problem has a number of important applications in operations research, economic equilibrium problems and in the engineering sciences. A variety of economic, biological and physical phenomena are most naturally modeled by saying that certain pairs of inequality constraints must be complementary, in the sense that at least one must hold with equality. This problem has attracted much attention due its various applications. For a non exhaustive description of these applications, see for instance Elfoutayeni et al. [7, 8, 9, 10, 11, 12], Ferris and Pang [13] and Garcia and Gould [14].

Many direct or iterative methods for solving LCP are proposed by several authors Cottle and Dantzig [1], Cottle et al. [2], Eaves and Lemke [3], Eaves and Scarf [4], Kelly and Watson [15], Lemke [17] and Watson [23].

The ideas presented by Lemke [17] were later exploited by Scarf [21] for developing fixed point algorithms. The relationship between the and the fixed point problem is well described by Eaves and Lemke [3] and by Eaves and Scarf [4].

Recently, in [5], we have built an interior point method to solve a linear complementarity problem for some matrix and ; the convergence of this method requires number of iterations where is the length of a binary coding of the input data of the problem ; the method developed in [5] is globally efficient and has a good iteration complexity but it has the problem of finding a strictly feasible starting point.

In [6], we have developed a globally convergent hybrid method which is based on vector divisions for solving the and we have given some numerical simulations to illustrate our theoretical results and to show that this method can solve large-scale linear complementarity problems.

Most studies to date have used the fact that solving linear complementarity problem LCP(A,b) requires the existence and uniqueness of the solution (the matrix is assumed to be symmetric positive definite or, at least, ) see, e.g., Cottle et al. [2], Elfoutayeni and Khaladi [5, 6], Kelly and Watson [15], Murty [18, 19] and Watson [23].

The aim of this work is to answer the following questions: (a) Under what conditions of A and b the problem LCP(A,b) has solutions? (b) How to calculate the solutions when they exist?

The paper is organized as follows. In the next section, we recall some notations and preliminary definitions to be used through the paper. In section 3, we provide the main result of the paper. The numerical examples are shown in Section 4. Section 5 concludes the paper.

2. Preliminaries

We first give some general notations and preliminary definitions to be used through the paper. For any positive integer , denotes the dimensional real Euclidean space and be the set of all real matrices. We will use to denote the identity matrix. The transpose of a vector is denoted by (with super script ). Given , , stands for the inner product of and . We denote . For , refers to the element of . Let , , the expression (respectively ) meaning that (respectively ) for each .

If is a matrix, we will denote by , the column vector of .

is said to be a if has a solution for each .

is said to be a if all its principal subdeterminants are positive. To test whether a given square matrix , of order , is a directly would require the computation of the determinants of principal submatrices of .

A key result in complementarity theory is that has a unique solution for each if and only if is a (see Samelson et al. [20]). Refining this characterization, Murty introduced the notion of a finite test set for : if the has a unique solution for each vector in the collection

where is any vector in the interior of some complementary cone, then is a and hence the has a unique solution for each . Note that has (4n+1) select elements.

Tamir [22] studied the set

of cardinality (3n +1). He found that was sufficient for testing whether or not is a P-matrix. Kostreva [16] refined the above characterization by proving that is a if and only if has a unique solution for each in the set where has cardinality (2n+2) and .

In what follows, we consider the general case where the matrix A is not necessarily a . To do so, we are going to need the following definitions:

Definition1 Given , let , be a subset of . denotes the submatrix of having rows indexed by elements of and columns indexed by elements of .

We denote by the principal submatrix .

Definition2 Given , let be a subset of . denotes the subvector of with rows indexed by elements of .

3. The Characterization of the Solutions

Using the above we now obtain our main result.

Theorem For a given matrix and a vector the following are equivalent

•  has a solution,

• There is a set such that the system of linear equations has a nonnegative solution and where denotes .

Proof. Let be a solution of the , i.e.,

, and

then we have

, and for all

Thus, if one of the variables in the pair , is positive, the other should be zero. Hence or for all

Let

and

is the complement of in the set .

There are two possible cases for X:

• , i.e. , therefore .

Thus, if then is a solution of .

Otherwise, there is such that

then can not be a solution of ,

and therefore .

• , i.e. for all that is

for all

So, satisfies the system .

Now for all

we have

or in matrix form

Thus, in both cases, there is a set such that the system of linear equations has a nonnegative solution:

and

with conventionally .

Now we assume that there is a set such that the system of linear equations has a nonnegative solution and .

Let and

where and , it can easily be verified that , and and therefore is a solution of the . This concludes the proof.

As an immediate consequence of previous Theorem we have the following result.

Corollary For a given matrix and a vector . has a unique solution if and only if either there is a unique set such that

• The matrix is invertible,

• ,

• 

or there are many sets with the same solution associated to all the sets .

Proof. This is immediate from the above Theorem, it suffices to note that has a unique solution if and only if we have one of the two following cases, in the first one, even if there are many sets there is always only one solution associated with these sets , in the second one, there is a unique set such that the system of linear equations has a unique nonnegative solution and , this is equivalent to that

on the one hand, the matrix is invertible

and

therefore

on the other hand

implies that

Therefore

This completes the proof.

In the following section we will give numerical examples where we can find many sets associated to a unique solution (example 1 and 2). We also give an example where a set X is associated to many solutions (example 3).

4. Numerical Examples

In this section, we provide numerical examples to illustrate the results given below. As announced, the first and the second one illustrate the situation where many subsets X are associated to a unique solution In the third one we obtain a set X associated to an infinity of solutions. Finally, the LCP given in the fourth example has no solution.

Example1 Consider the following linear complementarity problem

where and .

Let (resp. ), the solution of the system of linear equations is given by

(resp. ),

therefore, we have , i.e.,

(resp.).

For the other subsets of N it is easy to show that there is no solution in each case, to verify that, one need only verified that in each case, whether the solution of

is not nonnegative ,

or else () is not nonnegative.

Thus, this problem has one and only one solution, this solution is given by .

Example2 Let us consider the following linear complementarity problem , find a vector satisfying and

where and .

• Let

then we have

is the solution of the system of linear equations

Moreover

Thus, is a solution of this example.

• Let

then we have

is the solution of the system of linear equations

moreover

Thus, is a solution of this example.

• Let

then we have

is the solution of the system of linear equations

and of course in this case .

Thus, is a solution of this example.

Example3 Consider the following linear complementarity problem , find a vector satisfying and

where and .

Let then the system of linear equations associated with this set is , it is clear that the solutions of this system is the set ,

moreover

where is any real number in .

Example4 Let us consider the following linear complementarity problem , find a vector satisfying and

where and .

It is easy to show that there is no solution of this problem. To verify that, one need only consider the sets

and verify that in each case, whether the solution of is not nonnegative or else () is not nonnegative.

5. Conclusion

In this paper we have given a general characterization of a linear complementarity problem. We have demonstrated that has a solution if and only if there is a set such that the system of linear equations has a nonnegative solution and ; this solution is then given by where if , and if. We then have given numerical examples and we have used our characterization to provide the solutions. We point out that we can find many sets associated to a unique solution and on the contrary, we can find a set associated to many solutions.

We showed also that, if there is a unique set such if the system of linear equations has a unique nonnegative solution and

then the has a unique solution.

References

[1]  R. W. Cottle, G. B. Dantzig, A life in mathematical programming, Math. Program., 105 (2006) 1-8.
In article      CrossRef
 
[2]  R. W. Cottle, J. S. Pang, R. E. Stone, The Linear Complementarity Problem, Academic Press, New York, 1992.
In article      
 
[3]  B. C Eaves, C. E. Lemke, Equivalence of LCP and PLS, Math. Oper. Res., 6 (1981) 475-484.
In article      CrossRef
 
[4]  B. C Eaves, H. Scarf, The solution of systems of piecewise linear equations, Math. Oper. Res., 1 (1976) 1-27.
In article      CrossRef
 
[5]  Y. ELFoutayeni, M. Khaladi, A New Interior Point Method for Linear Complementarity Problem, Appl. Math. Sci., 4 (2010) 3289-3306.
In article      
 
[6]  Y. ELFoutayeni, M. Khaladi, Using vector divisions in solving the linear complementarity problem, J. Comput. Appl. Math., 236 (2012) 1919-1925.
In article      CrossRef
 
[7]  Y. ELFoutayeni, M. Khaladi, A. ZEGZOUTI, Profit maximization of fishermen exploiting two fish species in competition, accepted for publication.
In article      
 
[8]  Y. ELFoutayeni, M. Khaladi, A. Zegzouti, A generalized Nash equilibrium for a bioeconomic problem of fishing, Studia Informatica Universalis-HERMANN, 10 (2012) 186-204.
In article      
 
[9]  Y. ELFoutayeni, M. Khaladi, A bio-economic model of fishery where prices depend harvest, J. Adv. Model. Optim., 14 (2012) 543-555.
In article      
 
[10]  Y. ELFoutayeni, M. Khaladi, A generalized bio-economic model for competing multiple-fish populations where prices depend on harvest, J. Adv. Model. Optim., 14 (2012) 531-542.
In article      
 
[11]  Y. ELFoutayeni, M. Khaladi, Prey Switching: How to maximize the species's well being, J. Adv. Model. Optim., 14 (2012) 577-587.
In article      
 
[12]  Y. ELFoutayeni, Modélisation et étude mathématique et informatique d’un modèle bioéconomique d’exploitation d’espèces marines en compétition, thèse Université Cadi Ayyad, Marrakech Maroc.
In article      
 
[13]  M. C. Ferris, J. S. Pang, Engineering and economic applications of complementarity problems, SIAM Rev., 39 (1997) 669-713.
In article      CrossRef
 
[14]  C. B. Garcia, F. J. Gould, Studies in linear complementarity, Center for Mathematical Studies in Business and Economics, University of Chicago, Chicago (1980).
In article      
 
[15]  L. M. Kelly, L. T. Watson, Q-Matrices and Spherical Geometry, Linear Geometry and its Applications, 25 (1979) 175-189.
In article      
 
[16]  M. M. Kostreva, Finite test sets and P-matrices, Proc. Amer. Math. Soc., 84 (1982) 104-105.
In article      
 
[17]  C. E. Lemke, Bimatrix equilibrium points and mathematical programming, Manag. Sci., 11 (1965) 681-689.
In article      CrossRef
 
[18]  K. G. Murty, On a characterization of P-matrices, SIAM J Appl Math, 20 (1971) 378-384.
In article      CrossRef
 
[19]  K. G. Murty, On the number of solutions to the complementarity problem and spanning properties of complementary cones, Linear Algebra and Appl., 5 (1972) 65-108.
In article      CrossRef
 
[20]  H. Samelson, R. M. Thrall, O. Wesler, A partition theorem for Euclidean n-space, Proc. Amer. Math. Soc., 9 (1958) 805-807.
In article      
 
[21]  H. Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math., 15 (1967) 1328-1342.
In article      CrossRef
 
[22]  A. Tamir, on a characterization of P-matrices, Math. Programming, 4 (1973) 110-112.
In article      CrossRef
 
[23]  L. T. Watson, A variational Approach to the Linear Complementarity Problem, Doctoral Dissertation, Dept. of Mathematics, University of Michigan, Ann Arbor, MI, 1974.
In article      
 
comments powered by Disqus
  • CiteULikeCiteULike
  • MendeleyMendeley
  • StumbleUponStumbleUpon
  • Add to DeliciousDelicious
  • FacebookFacebook
  • TwitterTwitter
  • LinkedInLinkedIn