An Asymptotical $O((k + 1)n^3L)$ Affine Scaling Algorithm for the $P_*(k)$-Matrix Linear Complementarity Problem (Journal of Computational Mathematics, 2001)
Based on the generalized Dikin-type direction proposed by Jansen et al in 1997, we give out in this paper a generalized Dinkin-type affine scaling algorithm for solving the $P_*(k)$-matrix linear complementarity problem (LCP). By using high-order correctors technique and rank-one updating, the iteration complexity and the total computational turn out asymptotically $O((κ+1)\sqrt{n}L)$ and $O((κ+1)n^3L)$ respectively.
Keywords: linear complementarity problem; $P_*(K)$-matrix; affine scaling algorithm.