Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

General Characterization of a Linear Complementarity Problem

Youssef Elfoutayeni*, Mohamed Khaladi

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

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.

Keywords: linear complementarity problem, system of linear equations, P-matrix, principal sub-matrix, general characterization

Received December 13, 2012; Revised May 04, 2013; Accepted May 05, 2013

Citation: Youssef Elfoutayeni, Mohamed Khaladi, General Characterization of a Linear Complementarity Problem. American Journal of Modeling and Optimization, 1 (1). 1-5. January 2013. doi:10.12691/ajmo-1-1-1

1. Introduction

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

[picture] | (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

[picture] | (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.
[2]   | R. W. Cottle, J. S. Pang, R. E. Stone, The Linear Complementarity Problem, Academic Press, New York, 1992.
[3]   | B. C Eaves, C. E. Lemke, Equivalence of LCP and PLS, Math. Oper. Res., 6 (1981) 475-484.
[4]   | B. C Eaves, H. Scarf, The solution of systems of piecewise linear equations, Math. Oper. Res., 1 (1976) 1-27.
[5]   | Y. ELFoutayeni, M. Khaladi, A New Interior Point Method for Linear Complementarity Problem, Appl. Math. Sci., 4 (2010) 3289-3306.
[6]   | Y. ELFoutayeni, M. Khaladi, Using vector divisions in solving the linear complementarity problem, J. Comput. Appl. Math., 236 (2012) 1919-1925.
[7]   | Y. ELFoutayeni, M. Khaladi, A. ZEGZOUTI, Profit maximization of fishermen exploiting two fish species in competition, accepted for publication.
[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.
[9]   | Y. ELFoutayeni, M. Khaladi, A bio-economic model of fishery where prices depend harvest, J. Adv. Model. Optim., 14 (2012) 543-555.
[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.
[11]   | Y. ELFoutayeni, M. Khaladi, Prey Switching: How to maximize the species's well being, J. Adv. Model. Optim., 14 (2012) 577-587.
[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.
[13]   | M. C. Ferris, J. S. Pang, Engineering and economic applications of complementarity problems, SIAM Rev., 39 (1997) 669-713.
[14]   | C. B. Garcia, F. J. Gould, Studies in linear complementarity, Center for Mathematical Studies in Business and Economics, University of Chicago, Chicago (1980).
[15]   | L. M. Kelly, L. T. Watson, Q-Matrices and Spherical Geometry, Linear Geometry and its Applications, 25 (1979) 175-189.
[16]   | M. M. Kostreva, Finite test sets and P-matrices, Proc. Amer. Math. Soc., 84 (1982) 104-105.
[17]   | C. E. Lemke, Bimatrix equilibrium points and mathematical programming, Manag. Sci., 11 (1965) 681-689.
[18]   | K. G. Murty, On a characterization of P-matrices, SIAM J Appl Math, 20 (1971) 378-384.
[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.
[20]   | H. Samelson, R. M. Thrall, O. Wesler, A partition theorem for Euclidean n-space, Proc. Amer. Math. Soc., 9 (1958) 805-807.
[21]   | H. Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math., 15 (1967) 1328-1342.
[22]   | A. Tamir, on a characterization of P-matrices, Math. Programming, 4 (1973) 110-112.
[23]   | L. T. Watson, A variational Approach to the Linear Complementarity Problem, Doctoral Dissertation, Dept. of Mathematics, University of Michigan, Ann Arbor, MI, 1974.