Abstract:

Based on modifying the search direction of neighborhoodfollowing interiorpoint algorithm for linear programming, a new infeasible predictorcorrector interiorpoint algorithm for P*(κ)linear complementarity problem (LCP) was presented. The facts that P*(κ)LCP is nonmonotone and the corresponding search directions is nonorthogonal make the convergence analysis of the presented algorithm more complex. We have obtained the best
known iteration complexity bound of the proposed algorithm so far, i.e., O((1+κ)^5/2nL), where κ is the handicap of the problem. Numerical results show that the algorithm is feasible.

Key words: linear complementarity problem, interiorpoint algorithm, predictorcorrector algorithm, polynomial complexity