Weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem

In this paper we propose a weighted-path-following interior-point algorithm to monotone mixed linear complementarity problem. The algorithm is based on a new technique for finding a class of search directions and the strategy of the central path. At each iteration, we only use full-Newton step. Finally, the currently best known iteration bound for the algorithm with a small-update method, namely, O(√nlog n/ε) is derived, which is as good as the bound for the linear optimization analogue.