A full-Newton step feasible weighted primal-dual interior point algorithm for monotone LCP

摘要

In this paper,wepropose aweighted short-step primal-dual interior point algorithm for solving monotone linear complementarity problem (LCP). The algorithm uses at each interior point iteration a full-Newton step and the strategy of the central path to obtain an ?-approximate solution of LCP. This algorithm yields the best currently well-known theoretical complexity iteration bound, namely, O(√n log n/?) which is as good as the bound for the linear optimization analogue. The implementation of the algorithm and the algorithm in Wang et al. (Fuzzy Inform Eng 54:479-487, 2009) is done followed by a comparison between these two obtained numerical results.