Optimization Online


A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem

Jean-Pierre Dussault (Jean-Pierre.Dussault***at***Usherbrooke.ca)
Mathieu Frappier (Mathieu.Frappier***at***usherbrooke.ca)
Jean Charles Gilbert (Jean-Charles.Gilbert***at***inria.fr)

Abstract: The plain Newton-min 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 M-matrix, but not when it is a P-matrix. When convergence occurs, it is often very fast (in at most n iterations for an M-matrix, 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 Newton-min direction that results in a jump over at least one of the encountered kinks of the min-function, 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 P-matrix), 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, Newton-min algorithm, nondegenerate matrix, P-matrix, semismooth Newton method

Category 1: Complementarity and Variational Inequalities

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 06/02/2018
Entry Accepted: 06/02/2018
Entry Last Modified: 05/25/2019

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 Optimization Society