Thumbnail

Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix

Gilbert, J. Charles; Ben Gharbia, Ibtihel (2012), Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix, Mathematical Programming, 134, 2, p. 349-364. http://dx.doi.org/10.1007/s10107-010-0439-6

View/Open
Type
Article accepté pour publication ou publié
Date
2012
Journal name
Mathematical Programming
Volume
134
Number
2
Publisher
Springer
Pages
349-364
Publication identifier
Metadata
Show full item record
Author(s)
Gilbert, J. Charles
Ben Gharbia, Ibtihel cc
Abstract (EN)
The plain Newton-min algorithm to solve the linear complementarity problem (LCP for short) 0 £ x^(Mx+q) ³ 00x(Mx+q)0 can be viewed as a semismooth Newton algorithm without globalization technique to solve the system of piecewise linear equations min(x, Mx + q) = 0, which is equivalent to the LCP. When M is an M-matrix of order n, the algorithm is known to converge in at most n iterations. We show in this paper that this result no longer holds when M is a P-matrix of order ≥ 3, since then the algorithm may cycle. P-matrices are interesting since they are those ensuring the existence and uniqueness of the solution to the LCP for an arbitrary q. Incidentally, convergence occurs for a P-matrix of order 1 or 2.
Subjects / Keywords
Linear complementarity problem; Newton’s method; Nonconvergence; Nonsmooth function; M-matrix; P-matrix