Open Access Peer-reviewed

A Min-Max Algorithm for Solving the Linear Complementarity Problem

Youssef ELFOUTAYENI1, 2,, Mohamed KHALADI1, 2

1UMI UMMISCO, IRD - UPMC, Paris, France

2MPD Laboratory, UCAM, Marrakech, Maroc

Journal of Mathematical Sciences and Applications. 2013, 1(1), 6-11. DOI: 10.12691/jmsa-1-1-2
Published online: August 25, 2017


The Linear Complementarity Problem LCP(M,q) is to find a vector x in IRn satisfying x0, Mx+q0 and xT(Mx+q)=0, where M as a matrix and q as a vector, are given data. In this paper we show that the linear complementarity problem is completely equivalent to finding the fixed point of the map x = max (0, (I-M)x-q); to find an approximation solution to the second problem, we propose an algorithm starting from any interval vector X(0) and generating a sequence of the interval vector (X(k))k=1 which converges to the exact solution of our linear complementarity problem. We close our paper with some examples which illustrate our theoretical results.


linear complementarity problem, min-max algorithm, fixed point, Brouwer theorem, interval vector, closed bounded convex set
[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.View Article
[2]  R. W. Cottle, G. B. Dantzig, A life in mathematical programming, Math. Program., 105 (2006) 1-8.View Article
[3]  B. C Eaves, Homotopies for the computational of fixed points, Math. Program., 3 (1972) 1-22.View Article
[4]  B. C Eaves, C. E. Lemke, Equivalence of LCP and PLS, Math. Oper. Res., 6 (1981) 475-484.View Article
[5]  B. C Eaves, R. Saigal, Homotopies for computational of fixed points on unbounded regions, Math. Program., 3 (1972) 225-237.View Article
[6]  B. C Eaves, H. Scarf, The solution of systems of piecewise linear equations, Math. Oper. Res., 1 (1976) 1-27.View Article
[7]  Y. Elfoutayeni, M. Khaladi, A New Interior Point Method for Linear Complementarity Problem, Appl. Math. Sci., 4 (2010) 3289-3306.
[8]  Y. ELFoutayeni, M. Khaladi, Using vector divisions in solving the linear complementarity problem, J. Comput. Appl. Math., 236 (2012) 1919-1925.View Article
[9]  Y. ELFoutayeni, M. Khaladi, A. ZEGZOUTI, Profit maximization of fishermen exploiting two fish species in competition, submitted for publication.
[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.
[11]  Y. ELFoutayeni, M. Khaladi, A bio-economic model of fishery where prices depend harvest, J. Adv. Model. Optim., 14 (2012) 543-555.
[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.
[13]  Y. ELFoutayeni, M. Khaladi, Prey Switching: How to maximize the species’s well being, J. Adv. Model. Optim., 14 (2012) 577-587.
[14]  Y. ELFoutayeni, M. Khaladi, Gauss-Seidel-He method for solving a complementarity problems, submitted for publication.
[15]  Y. ELFoutayeni, M. Khaladi, General Characterization of a Linear Complementarity Problem, submitted for publication.
[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.
[17]  M. L. Fisher, P. J. Gould, A simplicial algorithm for the nonlinear complementarity problem, Math. Program., 6 (1974) 281-300.View Article
[18]  C. B. Garcia, The complementarity problem and its application, Ph. D. Thesis, Rensselaer Polytechnic Institute, Troy, NY (1973).
[19]  M. Kojima, Computational methods for solving the nonlinear complementarity problem, Keio Engineering Reports 27, Keio University, Yokohama, Japan (1974). PubMed
[20]  C. E. Lemke, Bimatrix equilibrium points and mathematical programming, Manag. Sci., 11 (1965) 681-689.View Article
[21]  H. J. Lüthi, A simplicial approximation of a solution for the nonlinear complementarity problem, Math. Program., 9 (1975) 278-293.View Article
[22]  O. L. Mangasarian, Equivalence of the Complementarity Problem to a System of Nonlinear Equations, SIAM J. Appl. Math., 31-1 (1976) 89-92.
[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).
[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.View Article
[25]  H. Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math., 15 (1967) 1328-1342.View Article
[26]  L. T. Watson, Solving the Nonlinear Complementarity Problem by Homotopy Method, SIAM J. Control Optim. 17 (1979) 36-46.View Article