Skip to Main content Skip to Navigation
Journal articles

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

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.
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download

https://hal.inria.fr/hal-01806399
Contributor : Jean Charles Gilbert <>
Submitted on : Saturday, May 25, 2019 - 11:24:27 AM
Last modification on : Wednesday, February 10, 2021 - 12:32:02 PM

File

dussault-frappier-gilbert-2019...
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License

Identifiers

Collections

Citation

Jean-Pierre Dussault, Mathieu Frappier, Jean Charles Gilbert. 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. EURO Journal on Computational Optimization, Springer, 2019, 7 (4), pp.22. ⟨10.1007/s13675-019-00116-6⟩. ⟨hal-01806399v2⟩

Share

Metrics

Record views

103

Files downloads

660