A New Polynomial Interior-Point Algorithm for Monotone Mixed Linear Complementarity Problem

摘要

In this paper a new polynomial interior-point algorithm for monotone mixed linear complementarity problem is presented. 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 use only full-Newton step. Moreover, we obtain the currently best known iteration bound for the algorithm with small-update method, namely,$O(sqrt{n}log{frac{n}{epsilon}})$, which is as good as the linear analogue.