A Predictor-Corrector Method for Solving the P*-matrix LCP from Infeasible Starting Points

A predictor-corrector method for solving the P ()-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 \Gamma ( + 1) 2 nL \Delta 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 (( + 1) p nL) iterations. The algorithm is quadratically convergent for problems having a strictly complementary solution. Key Words: linear complementarity problems, P -matrices, predictor-corrector, infeasibleinterior -point algorithm, polynomiality, superlinear convergence. Abbreviated Title: A predictor--corrector method for LCP. Department of Mathematics and Computer Science, Valdosta State University..