A new predictor–corrector algorithm is proposed for solving P*(κ)-matrix linear complementarity problems. If the problem is solvable, then the algorithm converges from an arbitrary positive starting point (x0, s0). The computational complexity of the algorithm depends on the quality of the starting point. If the starting point is feasible or close to being feasible, it has O((1 + κ) √((n/ρ0))L)-iteration complexity, where ρ0 is the ratio of the smallest and average coordinate of x0s0. With appropriate initialization, a modified version of the algorithm terminates in O((1 + κ)2(n/ρ0)L) steps either by finding a solution or by determining that the problem has no solution in a predetermined, arbitrarily large, region. The algorithm is quadratically convergent for problems having a strictly complementary solution. We also propose an extension of a recent algorithm of Mizuno to P*(κ)-matrix linear complementarity problems such that it can start from arbitrary positive points and has superlinear convergence without a strictly complementary condition.
