A Mehrotra-type Predictor-corrector Algorithm for Monotonic Linear Complementarity Problem

Mehrotra-type predictor-corrector algorithms are the backbone of most Interior Point Methods based software packages. Recently Salahi et al. have considered a variant of Mehrotra's celebrated predictor-corrector algorithm for linear optimization problem. By a numerical example they showed that this variant might make very small steps in order to keep the iterate in a certain neighborhood of the central path, which implies the inefficiency of the algorithm, This observation motivated them to incorporate a safeguard in their algorithmic scheme that gives a lower bound for the step size at each iteration and thus imply polynomial iteration complexity. This paper extends their approach to the monotonic linear complementarity problem. As the search directions Delta x and Delta s aren't orthogonal any more, the complexity analysis of this method is different from that of linear programming, correspondingly. We proved that the extended algorithm, in the worst case, will terminate after at most O (n(2) log (x(O))(T)9(O)/E) iterations and the computational result indicate that our algorithm is efficient.