A complexity analysis of a smoothing method using CHKS-functions for monotone linear complementarity problems

We consider the standard linear complementarity problem (LCP): Find (x, y) is an element of R-2n such that y = Mx + q, (x, y) greater than or equal to 0 and x(i)y(i) = 0 (i = 1, 2, ... , n), where M is an n x n matrix and q is an n-dimensional vector. Recently several smoothing methods have been developed for solving monotone and/or P-0 LCPs. The aim of this paper is to derive a complexity bound of smoothing methods using Chen-Harker-Kanzow-Smale functions in the case where the monotone LCP has a feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. As a consequence, we show that the algorithm terminates in O (<(<gamma>)over bar>(6)n/epsilon (6) log <(<gamma>)over bar>(2)n/epsilon (2)) Newton iterations where <(<gamma>)over bar> is a number which depends on the problem and the initial point. We also discuss some relationships between the interior point methods and the smoothing methods.