A predictor-corrector method for solving the P*(kappa)-matrix LCP from infeasible starting points

A predictor-corrector method for solving the P*(kappa)-matrix linear complementarity problems from infeasible starting points is analyzed. Two matrix factorizations and two backsolves are performed at each iteration. The algorithm terminates in O((kappa+1)(2)nL) steps either by finding a solution or by determining that the problem is not solvable. The computational complexity depends on the quality of the starting points. If the problem is solvable and if a certain measure of feasibility at the starting point is small enough then the algorithm finds a solution in O((kappa+1)root nL) iterations. The algorithm is quadratically convergent for problems having a strictly complementary solution.