Convergence analysis of an infeasible interior point algorithm based on a regularized central path for linear complementarity problems

Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P*LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence is globally linear and it achieves e-feasibility and e-complementarity in at most O(n²1n(1/e)) iterations with a properly chosen starting point.