Mehrotra-type predictor–corrector algorithms for sufficient linear complementarity problem

Two Mehrotra-type predictor–corrector algorithms are proposed for solving sufficient linear complementarity problems. Both algorithms are independent on the handicap χ of the problems. The first version of the Mehrotra-type algorithm is a generalization of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. [M. Salahi, J. Peng, T. Terlaky, On Mehrotra-type predictor–corrector algorithms, SIAM J. Optim. 18 (2007) 1377–1397]. We also present a new variant of Mehrotra-type predictor–corrector algorithm using a new adaptive updating strategy of the centering parameter. We show that both algorithms enjoy O ( n ( 1 + χ ) log ( ( x 0 ) T s 0 / ϵ ) ) iteration complexity. Some numerical results are reported as well.