An Infeasible Interior-Point Algorithm for Solving Linear Complementarity Problems

A new infeasible-interior-point algorithm for solving linear complementarity problems requiring one feasibility step and three centering steps. The algorithm starts from strictly feasible iterates of a perturbed problem, on its central path, and feasibility step finds 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 central path of the new perturbed problem. The starting point depends on two positive number p, and o, . The algorithm terminates either by finding an e-solution ordetecting that the LCP problem has no optimal solution with vanishing duality gap satisfying a condition in terms of p, and p, . The iteration bound coincides with the currently best iteration boundfor linear complementarity problems.

Keywords:

Linear complementarity problem , infeasible interior-point methods , central path , polynomialcomplexity