  


A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newtonmin algorithm for solving the linear complementarity problem
JeanPierre Dussault (JeanPierre.DussaultUsherbrooke.ca) Abstract: The plain Newtonmin algorithm for solving the linear complementarity problem (LCP) 0 ≤ x ⊥ (Mx+q) ≥ 0 can be viewed as an instance of the plain semismooth Newton method on the equational version min(x,Mx+q) = 0 of the problem. This algorithm converges for any q when M is an Mmatrix, but not when it is a Pmatrix. When convergence occurs, it is often very fast (in at most n iterations for an Mmatrix, where n is the number of variables, but often much faster in practice). In 1990, Harker and Pang proposed to improve the convergence ability of this algorithm by introducing a stepsize along the Newtonmin direction that results in a jump over at least one of the encountered kinks of the minfunction, in order to avoid its points of nondifferentiability. This paper shows that, for the Fathi problem (an LCP with a positive definite symmetric matrix M, hence a Pmatrix), an algorithmic scheme, including the algorithm of Harker and Pang, may require n iterations to converge, depending on the starting point. Keywords: Iterative complexity, linear complementarity problem, Fathi and Murty problems, globalization, Harker and Pang algorithm, line search, Newtonmin algorithm, nondegenerate matrix, Pmatrix, semismooth Newton method Category 1: Complementarity and Variational Inequalities Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization ) Citation: Download: [PDF] Entry Submitted: 06/02/2018 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  