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 Salahiet 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 verysmall 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 as 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 Deltax and Deltas 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 O(n² log (x⁰)^Ts⁰/epsiv) and the computational result indicate that our algorithm is efficient.