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

• 成果类型: Article
• 署名作者: Ben Gharbia, Ibtihel; Gilbert, J. Charles
• 署名单位: Universite PSL; Universite Paris-Dauphine
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-010-0439-6
• 发表日期: 2012
• 页码: 349-364
• 关键词: active set strategy; semismooth

摘要

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 a parts per thousand yen 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.