A full-Newton step O(n)O(n) infeasible-interior-point algorithm for linear complementarity problems

This paper consists of two parts. In the first part we present a new primal-dual feasible interior-point algorithm for solving monotone linear complementarity problems (LCP). Since the algorithm uses only full-Newton steps, it has the advantage that no line-searches are needed. It is proven that the number of iterations of the algorithm is O(nlognε), which coincides with the well-known best iteration bound for LCP. In the second part, we generalize an infeasible interior-point method for linear optimization introduced by Roos (2006) [15] to LCP. Two types of full-Newton steps are used, feasibility steps and (ordinary) centering steps, respectively. The algorithm starts from strictly feasible iterates of a perturbed problem, on its central path, and feasibility steps find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain strictly feasible iterates close enough to the central path of the new perturbed problem. The starting point depends on two positive numbers ρpρp and ρdρd. The algorithm terminates either by finding an εε-solution or detecting that the LCP problem has no optimal solution with vanishing duality gap satisfying a condition in terms of ρpρp and ρdρd. The iteration bound coincides with the currently best iteration bound for linear complementarity problems.