1. Introduction

T The Complementarity Problem noted () is a classical problem from optimization theory of finding such that

(1)

where , a continuous operator from into itself, is given data.

The contraint is called the complementarity condition since for any , if , and vice versa. It may be the case that however.

This problem becomes in present the subject of much research important because it arises in many areas and it includes important fields, we cite for example the linear programming (), the nonlinear programming (), the convex quadratic programming and the variational inequalities problems.

In the case that the function is a nonlinear continuous operator from into itself, so it is called a NonLinear Complementarity Problem associated with the function and noted . Numerous methods and algorithms exist to solve nonlinear complementarity problems such as the homotopy methods of Merrill ^[23] and several other authors (see for example Eaves et al. ^{[3, 5]}, Saigal ^[24]), using a reformulation of the due to Mangasarian ^[22] in which the zero finding problem can be made as smooth as desired, Watson ^[26] applied the homotopy or continuation method of Chow, Mallet-Paret and Yorke ^[1] to solve the problem. Instead of reformulating the as a zero finding problem, other authors adjusted simplicial fixed point algorithms to solve the directly, see e.g. Fisher and Gould ^[17], Garcia ^[18], Kojima ^[19] or Lüthi ^[21] and recently our modest work Elfoutayeni and Khaladi ^[14], In this paper we have given a new method for solving this problem which converges very rapidly relative to most of the existing methods and does not require a lot of arithmetic operations to converge. For this we have showed that solving the is equivalent to solving where is a function from into itself defined by . After that we have built a sequence of smooth functions which is uniformly convergent to the function and we have showed that an approximation of the solution of the is obtained by solving for a parameter large enough. For solving the system of nonlinear equations we have used the Gauss-Seidel-He algorithm. The numerical results obtained in this paper are very favorable and showed that our method works well for the problems tested.

In the case that the function is affine, i.e., its accurate form as below , where is an element of and is a real square matrix of order , so it is called a Linear Complementarity Problem associated with the matrix and the vector and noted . To solve this problem, there are several methods and algorithms, we cite for example Lemke ^[20] first presented a solution for this problem. His ideas were later exploited by Scarf ^[25] in his work on fixed point algorithms. The relationship between the and the fixed point problem is well described by Eaves and Scarf^[6] and by Eaves and Lemke ^[4]. Cottle and Dantzig’s principal pivot method^[2] and recently our modest works Elfoutayeni and Khaladi ^{[7, 8]}. In the first one 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 . This interior point method is globally efficient and has a good iteration complexity but it has the problem of finding a strictly feasible starting point. In the second one we have given a globally convergent hybrid method which is based on vector divisions and the secant method for solving the ; we have given in this paper some numerical simulations to illustrate our theoretical results, and to show that this method can solve efficiently large-scale linear complementarity problems. We have to note that in our paper Elfoutayeni and Khaladi ^[15] we have given a general characterization of a linear complementarity problem. Furthermore, through this paper, we can provide the solution (if it exists) of this problem in a straightforward manner and according to the data. Precisely, 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 andthis solution is then given by where if , and if . We have to note that as one of the remarks we would like to point out that we can find many sets , but a unique solution and contrary, we can find a set but many solutions (we must think of the invertibility of the submatrix in each case). As a final remark we like to stress that the has a unique solution if and only if there is a unique set such that the system of linear equations has a unique nonnegative solution and.

In this paper we show that the linear complementarity problem is completely equivalent to finding the fixed point of the map ; to find an approximation solution to the second problem, we propose an algorithm starting from any interval vector and generating a sequence of the interval vector which converges to the exact solution of our linear complementarity problem. We close our paper with some examples which illustrate our theoretical results.

The paper is organized as follows. In section 2 we briefly give some definitions and notations to be used through the paper. In section 3 we write LCP in the equivalent form of finding a solution of a fixed point of the function . In section 4 we give some numerical examples and we give a conclusion in section5.

2. Preliminaries

In this section, we summarize some basic properties and related definitions which be used in the following discussion.

In particular, denotes the space of real dimensional vectors and the nonnegative orthant of .

Let , , is their inner product; is the Euclidean norm and is maximum norm. The vector is the vector of ones in .

For and a nonnegative integer, refers to the vector obtained after iterations; for , refers to the element of , and refers to the element of the vector obtained after iterations.

Let , , the expression (respectively ) meaning that (respectively ) for each .

The transpose of a vector is denoted by super script , such as the transpose of the vector is given by .

is a n-dimensional interval vector which and are two vectors in ; noted by: .

denotes the set of all interval vector in

Let be an interval vector in [, meaning that for each .

Let be a function from to then

For any an interval vector in , we define the function from into by: .

The notation meaning that and

Recall that the spectrum of the matrix is the set of its values and its spectral radius is given by such that.

3. Equivalent Reformulation of CP and Algorithm

Our first objective in this section is to show that if is a solution of () then is a fixed point of the map

(2)

and vise versa.

Proposition 1 Solving the complementarity problem is equivalent to finding the solution of .

Proof. Let be a solution of () and let’s consider the set

and the complementarity of defined by

then we have for each

and for each

then is a fixed point of the function .

Now let be a fixed point of the function , then we have .

Now if then we have and therefore i.e.,

else if then we have

In the two cases we have and , therefore is a solution of (). This concludes the proof.

Now we propose an algorithm generating a sequence of the interval vector in and tending to the fixed point of the function .

For this, we choice an interval vector in so large to ensure that .

We define the interval vector in at iteration by such that

(3)

It is easy to show that if is a solution of , then .

Now we show that

Proposition 2 If there is an in the set such that

(4)

then the solution of () is not existing in .

Remark If the solution of () is not existing in , we redefine the algorithm with a new larger than the older one.

Proof. Assume the contrary, i.e., we suppose there is a solution of the (), then , i.e., for each we have

thus

this contradicts (4).

Now we show that

Proposition 3 If

then there is a solution of () in .

Proof. To prove that let’s , then we have and is a closed bounded convex set of the , since the function is a continuous function from to itself then from Brouwer theorem, we know that there is a fixed point satisfied

Now we show that

Lemma For each interval vector in we have

Proof. For each we have

If

then

If

then

If

then

and if

then

this contradicts the fact that exist at least an integer such that This completes the proof of the lemma.

Now we provide a theorem to prove the convergence of the algorithm in the case where the function is linear, i.e., ; with is matrix and .

Theorem Let be a matrix satisfy that , if there is a solution of (2) in then

Proof. Using the fact (3) we have

(5)

and by previous lemma it follows that

Further, the matrix satisfied then

(6)

On the other hand if there is a solution of (2) in then , and from (3) we have ; if we use the simple principle, we can deduct that .

Therefore from (6) we have .

With the above ideas, we suggest the following algorithm for solving the linear complementarity problem.

Algorithm

• Initialization

an interval vector in ;

tolerance ;

• Iterative step

Step 1 Compute

Step 2 Compute

Step 3 If there is an in the set such that

then the solution is not existing in ; and therefore we redefine the algorithm with a new larger than the older one and go to step 1.

Else go to step 4.

Step 4 If then we obtain the solution and terminate the algorithm.

Otherwise and return to step 1.

4. Numerical tests

In this section, we provide numerical examples to demonstrate the efficiency of our algorithm. To test the efficiency of our proposed algorithm, we conducted the numerical experiments on some test problems.

In the following, we will implement our algorithm in Matlab and run it on a personal computer with a GHZ CPU processor and MB memory. We stop the iterations if the condition is satisfied.

Example 1 Let us consider the following linear complementarity problem , find a vector satisfying and where

and

The exact solution of this problem is . We have to note that .

When looking for an approximation with six significant digits, we obtain that, our algorithm requires

The test results of this example are summarized in Table 1.

Table 1. Numerical results for the first example with k=20

Download as

PowerPoint Slide

Larger image(png format)

Tables index

Veiw figure

View current table in a new window

View next table

The Table 1 shows that the numerical results using a min-max algorithm to solve this linear complementarity problem.

Example 2 Consider the following class of linear complementarity problems: For a given integer , find a vector in satisfying

, and

where where is the Kronecker’s delta ( and if ) and where .

We have to note that . This example is used by Elfoutayeni and Khaladi ^[14].

The exact solution of this problem is .

When looking for an approximation with six significant digits, we obtain that, our algorithm requires:

CPU time = 0,077805 s, for n=3

CPU time = 0,169023 s, for n=5

CPU time = 0,275408 s, for n=7

The test results of this example are summarized in Table 2.

Table 2. Numerical results for the second example

Download as

PowerPoint Slide

Larger image(png format)

Tables index

Veiw figure

View current table in a new window

View previous table

The Table 2 shows that the numerical results using a min-max algorithm to solve this linear complementarity problem.

5. Conclusion

In this paper we have demonstrated that, on the one hand, solving the linear complementarity problem is equivalent to finding the fixed point of the system ; on the other hand, we have described an algorithm for finding an approximation solution to the fixed point of the second problem; this algorithm starting from any interval vector and generating a sequence of the interval vector satisfying where is the exact solution of linear complementarity problem. The numerical results indicate that our algorithm works reliably and efficiently.

References

[1]	S. N. Chow, J. Mallet-Paret, J. A. Yorke, Finding zeros of maps: homotopy methods that are constructive with probability one, Math. Comp., 32 (1978) 887-899.
	In article		CrossRef
[2]	R. W. Cottle, G. B. Dantzig, A life in mathematical programming, Math. Program., 105 (2006) 1-8.
	In article		CrossRef
[3]	B. C Eaves, Homotopies for the computational of fixed points, Math. Program., 3 (1972) 1-22.
	In article		CrossRef
[4]	B. C Eaves, C. E. Lemke, Equivalence of LCP and PLS, Math. Oper. Res., 6 (1981) 475-484.
	In article		CrossRef
[5]	B. C Eaves, R. Saigal, Homotopies for computational of fixed points on unbounded regions, Math. Program., 3 (1972) 225-237.
	In article		CrossRef
[6]	B. C Eaves, H. Scarf, The solution of systems of piecewise linear equations, Math. Oper. Res., 1 (1976) 1-27.
	In article		CrossRef
[7]	Y. Elfoutayeni, M. Khaladi, A New Interior Point Method for Linear Complementarity Problem, Appl. Math. Sci., 4 (2010) 3289-3306.
	In article
[8]	Y. ELFoutayeni, M. Khaladi, Using vector divisions in solving the linear complementarity problem, J. Comput. Appl. Math., 236 (2012) 1919-1925.
	In article		CrossRef
[9]	Y. ELFoutayeni, M. Khaladi, A. ZEGZOUTI, Profit maximization of fishermen exploiting two fish species in competition, submitted for publication.
	In article
[10]	Y. ELFoutayeni, M. Khaladi, A. Zegzouti, A generalized Nash equilibrium for a bioeconomic porblem of fishing, Studia Informatica Universalis-HERMANN, 10 (2012) 186-204.
	In article
[11]	Y. ELFoutayeni, M. Khaladi, A bio-economic model of fishery where prices depend harvest, J. Adv. Model. Optim., 14 (2012) 543-555.
	In article
[12]	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
[13]	Y. ELFoutayeni, M. Khaladi, Prey Switching: How to maximize the species’s well being, J. Adv. Model. Optim., 14 (2012) 577-587.
	In article
[14]	Y. ELFoutayeni, M. Khaladi, Gauss-Seidel-He method for solving a complementarity problems, submitted for publication.
	In article
[15]	Y. ELFoutayeni, M. Khaladi, General Characterization of a Linear Complementarity Problem, submitted for publication.
	In article
[16]	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
[17]	M. L. Fisher, P. J. Gould, A simplicial algorithm for the nonlinear complementarity problem, Math. Program., 6 (1974) 281-300.
	In article		CrossRef
[18]	C. B. Garcia, The complementarity problem and its application, Ph. D. Thesis, Rensselaer Polytechnic Institute, Troy, NY (1973).
	In article
[19]	M. Kojima, Computational methods for solving the nonlinear complementarity problem, Keio Engineering Reports 27, Keio University, Yokohama, Japan (1974).
	In article		PubMed
[20]	C. E. Lemke, Bimatrix equilibrium points and mathematical programming, Manag. Sci., 11 (1965) 681-689.
	In article		CrossRef
[21]	H. J. Lüthi, A simplicial approximation of a solution for the nonlinear complementarity problem, Math. Program., 9 (1975) 278-293.
	In article		CrossRef
[22]	O. L. Mangasarian, Equivalence of the Complementarity Problem to a System of Nonlinear Equations, SIAM J. Appl. Math., 31-1 (1976) 89-92.
	In article
[23]	O. H. Merrill, Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Non-Empty, Convex, Upper Semi-Continuous Point to set Mappings, Dept. of Industrial Engineering, Univ. of Michigan Technical Report No. 71-7 (1971).
	In article
[24]	R. Saigal, On the convergence rate of algorithms for solving equations that are based on methods of complementarity pivoting, Math. Oper. Res., 2 (1977) 108-124.
	In article		CrossRef
[25]	H. Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math., 15 (1967) 1328-1342.
	In article		CrossRef
[26]	L. T. Watson, Solving the Nonlinear Complementarity Problem by Homotopy Method, SIAM J. Control Optim. 17 (1979) 36-46.
	In article		CrossRef