Skip to Main content Skip to Navigation
Reports

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\leq x\perp(Mx+q)\geq0$ 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 $\Mmat$-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 $\Pmat$-matrix of order~$\geq\nobreak3$, since then the algorithm may cycle. $\Pmat$-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 $\Pmat$-matrix of order~$1$ or~$2$.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00442293
Contributor : Jean Charles Gilbert <>
Submitted on : Monday, September 27, 2010 - 6:05:32 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on: : Tuesday, December 28, 2010 - 2:57:11 AM

File

RR-7160-v3.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00442293, version 3

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.. RR-7160, 2010. ⟨inria-00442293v3⟩

Share