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

Abstract : The plain Newton-min algorithm to solve the linear complementarity problem (LCP for short) 0 ≤ x ⊥ (Mx+q) ≥ 0 can be viewed as a nonsmooth 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.
Document type :
Reports
Complete list of metadatas

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/inria-00442293
Contributor : Jean Charles Gilbert <>
Submitted on : Monday, December 17, 2012 - 5:09:34 PM
Last modification on : Friday, May 25, 2018 - 12:02:06 PM
Long-term archiving on : Sunday, December 18, 2016 - 3:56:12 AM

File

p.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00442293, version 5

Collections

Citation

Ibtihel Ben Gharbia, Jean Charles Gilbert. Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix --- The full report.. [Research Report] RR-7160, INRIA. 2012, pp.19. ⟨inria-00442293v5⟩

Share

Metrics

Record views

353

Files downloads

98