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 $$\left\| {{\text{min\{ }}x,y{\text{\} }}} \right\|_\infty \leqslant \varepsilon $$ in at most $$\mathcal{O}((2 + \beta )(1 + (1/l(M)))^2 \log ((1 + (1/2)\beta )\mu _0 )/\varepsilon ))$$ Newton iterations; here, β and µ0 depend on the initial point, l(M) depends on M, and ɛ> 0. When Mis symmetric and positive definite, the complexity bound is $$\mathcal{O}((2 + \beta )C^2 \log ((1 + (1/2)\beta )\mu _0 )/\varepsilon ),$$ where $$C = 1 + (\sqrt n /(\min \{ \lambda _{\min } (M),1/\lambda _{\max } (M)\} ),$$ and $$\lambda _{\min } (M),\lambda _{\max } (M)$$ are the smallest and largest eigenvalues of M.