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/2006
Entry Accepted: 09/20/2006
Entry Last Modified: 09/20/2006

Modify/Update this entry