An infeasible-start path-following method for monotone LCPs

As is known in interior-point methods, algebraically equivalent paths give rise to different trajectories to the optimal set, together with different line search strategies. In this paper, an infeasible-starting path-following method for linear complementarity problems is constructed based on a specific algebraic transformation ln(χsμ) = 0. The algorithm is given and the global Q-linear convergence is established, under minimal assumptions. Moreover, with properly chosen starting point and properly controlled stepsize, an ϵ-feasible and ϵ-complementary solution of the problem can be obtained in O(n2ln(1ϵ)) iterations.