关键词: complementarity problem, infeasible interior-point methods, full-Newton step, polynomial complexity

Abstract: This paper proposes an infeasible interior-point algorithm with full-Newton step for linear complementarity problem, which is an extension of Roos about linear optimization. The main iteration of the algorithm consists of a feasibility step and several centrality steps. At last, we prove that the algorithm has O(nlog n/ε) polynomial complexity, which coincides with the best known one for the infeasible interior-point algorithm at present.

Key words: complementarity problem, infeasible interior-point methods, full-Newton step, polynomial complexity