On the Convergence of an Iterative Method for Solving Linear Complementarity Problem with WGPSBD Matrix

Arup Kumar Das, Rwitam Jana, Deepmala -

Abstract

In this paper we propose an iterative and descent type interior point method to compute solution of linear complementarity problem LCP($q,A$)  given that $A$ is real square matrix and $q$ is a real vector. The linear complementarity problem includes many of the optimization problems and applications. In this context we consider the class of weak generalized positive subdefinite matrices (WGPSBD) which is a generalization of the class of generalized positive subdefinite (GPSBD) matrices. Though Lemke's algorithm is frequently used to solve small and medium size LCP($q,A$), Lemke's algorithm does not compute solution of all problems. It is known that Lemke's algorithm is not a polynomial time bound algorithm. We show that the proposed algorithm converges to the solution of LCP($q,A$) where $A$ belongs to WGPSBD class. A numerical example is illustrated to show the performance of the proposed algorithm.