A first order affine scaling method and two $m$th order affine scaling methods for solving monotone linear complementarity problems (LCP) are presented. All three methods produce iterates in a wide neighborhood of the central path. The first order method has $O(nL^2(\log nL^2)(\log\log nL^2))$ iteration complexity. If the LCP admits a strict complementary solution then both the duality gap and the iteration sequence converge superlinearly with Q-order two. If $m=\Omega(\log(\sqrt{n}L))$, then both higher order methods have $O(\sqrt{n})L$ iteration complexity. The Q-order of convergence of one of the methods is $(m+1)$ for problems that admit a strict complementarity solution while the Q-order of convergence of the other method is $(m+1)/2$ for general monotone LCPs.
Citation
Technical Report TR2006-31, Department of Mathematics and Statistics, University of Maryland Baltimore County, 1000 Hilltop Circle Baltimore, MD 21250, USA, September/2006.
Article
View Primal-dual affine scaling interior point methods for linear complementarity problems