Using vector divisions in solving the linear complementarity problem

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:236

Article

Elfoutayeni, Youssef^1,2  Khaladi, Mohamed² 

[1] Private Univ Marrakech, Sch Engn & Innovat, Dept Comp Sci, Marrakech, Morocco

[2] Cadi Ayyad Univ, Fac Sci Semlalia, Dept Math, Marrakech, Morocco

关键词: Linear complementarity problem;    Vector division;    Global convergence;    Newton's method;    Secant method;   

DOI  :  10.1016/j.cam.2011.11.001

来源: Elsevier

【 摘 要 】

The linear complementarity problem LCP(M, q) is to find a vector z in IRn satisfying z(T)(Mz + q) = 0, Mz + q >= 0, z >= 0, where M = (m(ij)) is an element of IRnxn and q is an element of IRn are given. In this paper, we use the fact that solving LCP(M, q) is equivalent to solving the nonlinear equation F (x) = 0 where F is a function from IRn into itself defined by F (x) = (M+I)x+(M-I)|x|+q. We build a sequence of smooth functions (F) over tilde (p, x) which is uniformly convergent to the function F (x). We show that, an approximation of the solution of the LCP(M, q) (when it exists) is obtained by solving (F) over tilde (p, x) = 0 for a parameter p large enough. Then we give a globally convergent hybrid algorithm which is based on vector divisions and the secant method for solving LCP(M, q). We close our paper with some numerical simulations to illustrate our theoretical results, and to show that this method can solve efficiently large-scale linear complementarity problems. (C) 2011 Elsevier B.V. All rights reserved.

【 授权许可】

Free