Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix --- The full report. - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2010

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

Résumé

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$.
Fichier principal
Vignette du fichier
p.pdf (490.53 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00442293 , version 1 (19-12-2009)
inria-00442293 , version 2 (11-04-2010)
inria-00442293 , version 3 (27-09-2010)
inria-00442293 , version 4 (28-12-2010)
inria-00442293 , version 5 (17-12-2012)

Identifiants

  • HAL Id : inria-00442293 , version 4

Citer

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, 2010. ⟨inria-00442293v4⟩

Collections

INRIA-RRRT
356 Consultations
401 Téléchargements

Partager

Gmail Facebook X LinkedIn More