Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a $P$-matrix
Ibtihel Ben Gharbia(Ibtihel.Ben_Gharbiainria.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.
Entry Submitted: 04/11/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|