General Characterization of a Linear Complementarity Problem

Youssef Elfoutayeni^1, and Mohamed Khaladi²

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

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

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

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

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

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.