- Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a $P$-matrix Ibtihel Ben Gharbia(Ibtihel.Ben_Gharbiainria.fr) Jean-Charles Gilbert(Jean-Charles.Gilbertinria.fr) 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 $M$-matrix of order~$n$, the algorithm is known to converge in at most $n$ iterations. We show in this note that this result no longer holds when $M$ is a $P$-matrix of order~$\geq\nobreak3$, 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$. Keywords: linear complementarity problem, Newton's method, nonconvergence, nonsmooth function, $M$-matrix, $P$-matrix. Category 1: Complementarity and Variational Inequalities Citation: Research Report RR-7160, INRIA, BP 105, 78153 Le Chesnay, France, April 10, 2010. Download: [Postscript][PDF]Entry Submitted: 04/11/2010Entry Accepted: 04/11/2010Entry Last Modified: 04/11/2010Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society.