Optimization Online


Primal-dual affine scaling interior point methods for linear complementarity problems

Florian A. Potra (potra***at***math.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society