Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2001-004 (April 10, 2001)
A Superlinearly Convergent Algorithm for the Monotone Nonlinear Complementarity Problem without Uniqueness and Nondegeneracy Conditions
by Hiroshige Dan, Nobuo Yamashita and Masao Fukushima
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 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, Dan and Fukushima presented a technique to identify whether a solution is degenerate or not. Using this technique, we construct a differentiable system of nonlinear equations whose solution is a solution of the original NCP. Moreover, we propose a hybrid algorithm which 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.