A superlinearly convergent algorithm for the monotone nonlinear complementarity problem without uniqueness and nondegeneracy conditions

• 成果类型: Article
• 署名作者: Dan, H; Yamashita, N; Fukushima, M
• 署名单位: Kyoto University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.27.4.743.298
• 发表日期: 2002
• 页码: 743-754

摘要

The purpose of this paper,is to present an algorithm for solving the monotone nonlinear complementarity problem (NCP) that enjoys superlinear convergence in a genuine sense without the uniqueness and nondegeneracy conditions. Recently, Yamashita and Fukushima (2001) proposed a method based on the proximal point algorithm (PPA) for monotone NCP. The method has the favorable property that a generated sequence converges to the solution set of NCP superlinearly. However, when a generated sequence converges to a degenerate solution, the subproblems may become computationally expensive and the method does not have genuine superlinear convergence. More recently, Yamashita et al. (2001) presented a technique to identify whether a solution is degenerate or not. Using this technique, we construct a differentiable system of nonlinear equations in which the solution is a solution of the original NCP. Moreover, we propose a hybrid algorithm that is based on the PPA and uses this system. We show that the proposed algorithm has a genuine quadratic or superlinear rate of convergence even if it converges to a solution that is neither unique nor nondegenerate.