  


Primaldual 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 Qorder two. If $m=\Omega(\log(\sqrt{n}L))$, then both higher order methods have $O(\sqrt{n})L$ iteration complexity. The Qorder of convergence of one of the methods is $(m+1)$ for problems that admit a strict complementarity solution while the Qorder of convergence of the other method is $(m+1)/2$ for general monotone LCPs. Keywords: linear complementarity, interiorpoint, affine scaling, large neighborhood, superlinear convergence Category 1: Complementarity and Variational Inequalities Category 2: Linear, Cone and Semidefinite Programming Citation: Technical Report TR200631, 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/2006 Modify/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  