### A Min-Max Algorithm for Solving the Linear Complementarity Problem

**Youssef ELFOUTAYENI**^{1, 2,}, **Mohamed KHALADI**^{1, 2}

^{1}UMI UMMISCO, IRD - UPMC, Paris, France

^{2}MPD Laboratory, UCAM, Marrakech, Maroc

*Journal of Mathematical Sciences and Applications*, **2013** 1 (1),
pp 6-11

DOI: 10.12691/jmsa-1-1-2

Received December 13, 2012; Revised March 20, 2013; Accepted March 23, 2013

Corresponding author: youssef_foutayeni@yahoo.fr |

## Cite This Article:

- ELFOUTAYENI, Youssef, and Mohamed KHALADI. "A Min-Max Algorithm for Solving the Linear Complementarity Problem."
*Journal of Mathematical Sciences and Applications*1.1 (2013): 6-11.

- ELFOUTAYENI, Y. , & KHALADI, M. (2013). A Min-Max Algorithm for Solving the Linear Complementarity Problem.
*Journal of Mathematical Sciences and Applications*,*1*(1), 6-11.

- ELFOUTAYENI, Youssef, and Mohamed KHALADI. "A Min-Max Algorithm for Solving the Linear Complementarity Problem."
*Journal of Mathematical Sciences and Applications*1, no. 1 (2013): 6-11.

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

The Linear Complementarity Problem *LCP(M,q)* is to find a vector *x* in IR^{n} satisfying *x*≥*0, Mx+q*≥*0* and *x*^{T}*(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. [ CrossRef ] |

[2] | R. W. Cottle, G. B. Dantzig, A life in mathematical programming, Math. Program., 105 (2006) 1-8. [ CrossRef ] |

[3] | B. C Eaves, Homotopies for the computational of fixed points, Math. Program., 3 (1972) 1-22. [ CrossRef ] |

[4] | B. C Eaves, C. E. Lemke, Equivalence of LCP and PLS, Math. Oper. Res., 6 (1981) 475-484. [ CrossRef ] |

[5] | B. C Eaves, R. Saigal, Homotopies for computational of fixed points on unbounded regions, Math. Program., 3 (1972) 225-237. [ CrossRef ] |

[6] | B. C Eaves, H. Scarf, The solution of systems of piecewise linear equations, Math. Oper. Res., 1 (1976) 1-27. [ CrossRef ] |

[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. [ CrossRef ] |

[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. [ CrossRef ] |

[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. [ CrossRef ] |

[21] | H. J. Lüthi, A simplicial approximation of a solution for the nonlinear complementarity problem, Math. Program., 9 (1975) 278-293. [ 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. |

[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. [ CrossRef ] |

[25] | H. Scarf, The approximation of fixed points of a continuous mapping, SIAM J. Appl. Math., 15 (1967) 1328-1342. [ CrossRef ] |

[26] | L. T. Watson, Solving the Nonlinear Complementarity Problem by Homotopy Method, SIAM J. Control Optim. 17 (1979) 36-46. [ CrossRef ] |