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 (), Mathieu Frappier () and Jean Charles Gilbert ()
Additional contact information
Jean-Pierre Dussault: Université de Sherbrooke
Mathieu Frappier: Université de Sherbrooke
Jean Charles Gilbert: INRIA Paris

EURO Journal on Computational Optimization, 2019, vol. 7, issue 4, No 2, 359-380

Abstract: Abstract The plain Newton-min algorithm for solving the linear complementarity problem (LCP) “$$0\leqslant x\perp (Mx+q)\geqslant 0$$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$$min(x,Mx+q)=0” of the problem. This algorithm converges for any q when M is an $$\mathbf{M }$$M-matrix, but not when it is a $$\mathbf{P }$$P-matrix. When convergence occurs, it is often very fast (in at most n iterations for an $$\mathbf{M }$$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 $$\mathbf{P }$$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; 15B99; 47B99; 49M15; 65K15; 90C33 (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-019-00116-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:eurjco:v:7:y:2019:i:4:d:10.1007_s13675-019-00116-6

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-019-00116-6

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().