- Primal-dual affine scaling interior point methods for linear complementarity problems Florian A. Potra (potramath.umbc.edu) Abstract: 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. Keywords: linear complementarity, interior-point, affine scaling, large neighborhood, superlinear convergence Category 1: Complementarity and Variational Inequalities Category 2: Linear, Cone and Semidefinite Programming Citation: Technical Report TR2006-31, Department of Mathematics and Statistics, University of Maryland Baltimore County, 1000 Hilltop Circle Baltimore, MD 21250, USA, September/2006. Download: [PDF]Entry Submitted: 09/20/2006Entry Accepted: 09/20/2006Entry Last Modified: 09/20/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.