Optimization Online


Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a $P$-matrix

Ibtihel Ben Gharbia(Ibtihel.Ben_Gharbia***at***inria.fr)
Jean-Charles Gilbert(Jean-Charles.Gilbert***at***inria.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/2010
Entry Accepted: 04/11/2010
Entry Last Modified: 04/11/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society