Complexity of a noninterior path-following method for the linear complementarity problem

We study the complexity of a noninterior path-following method for the linear complementarity problem. The method is based on the Chen–Harker–Kanzow–Smale smoothing function. It is assumed that the matrix M is either a P-matrix or symmetric and positive definite. When M is a P-matrix, it is shown that the algorithm finds a solution satisfying the conditions Mx−y+q=0 and ∥min{x,y}∥∞≤ϵ in at most O((2+β)(1+(1/l(M)))²log((1+(1/2)β)μ0)/ϵ)) Newton iterations; here, β and μ0 depend on the initial point, l(M) depends on M, and ϵ>0. When M is symmetric and positive definite, the complexity bound is O((2+β)C²log((1+(1/2)β)μ0)/ϵ), where C=1+(√n/(min{λmin(M), 1/λmax(M)}), and λmin(M), λmax(M) are the smallest and largest eigenvalues of M.