Nonconvergence of the plain Newton-min algorithm for linear complementarity problems with a P-matrix |
| |
Authors: | Ibtihel Ben Gharbia J. Charles Gilbert |
| |
Affiliation: | (3) Dept. Comput. & Software McMaster Univ., 1280 Main Street West, Hamilton, Ontario, Canada, L8S 4L7 |
| |
Abstract: | The plain Newton-min algorithm to solve the linear complementarity problem (LCP for short) can be viewed as a semismooth 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 paper that this result no longer holds when M is a P-matrix of order ≥ 3, 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: | |
本文献已被 SpringerLink 等数据库收录! |
|