  


Nonconvergence of the plain Newtonmin algorithm for linear complementarity problems with a $P$matrix
Ibtihel Ben Gharbia(Ibtihel.Ben_Gharbiainria.fr) Abstract: The plain Newtonmin 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 RR7160, INRIA, BP 105, 78153 Le Chesnay, France, April 10, 2010. Download: [Postscript][PDF] Entry Submitted: 04/11/2010 Modify/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  