Department of Applied Mathematics & Physics, Kyoto Univiversity

Technical Report #98013 (July, 1998)

A New Derivative-Free Descent Method for the Nonlinear Complementarity Problem
by Kenjiro Yamada, Nobuo Yamashita and Masao Fukushima

Recently, much effort has been made in solving and analyzing the nonlinear complementarity problem (NCP) by means of a reformulation of the problem as an equivalent unconstrained optimization problem involving a merit function. In this paper, we propose a new merit function for the NCP and show several favorable properties of the proposed function. In particular, we give conditions under which the function provides a global error bound for the NCP and conditions under which its level sets are bounded. Moreover, we propose a new derivative-free descent algorithm for solving the NCP based on this function. We show that any accumulation point generated by the algorithm is a solution of the NCP under the monotonicity assumption on the problem. Also, we prove that the sequence generated by the algorithm converges linearly to the solution under the strong monotonicity assumption. The most interesting feature of the algorithm is that the search direction and the stepsize are adjusted simultaneously during the linesearch process, whereas a fixed search direction is used in the linesearch process in earlier derivative-free algorithms proposed by Geiger and Kanzow, Jiang, Mangasarian and Solodov, and Yamashita and Fukushima. Making use of this particular feature, we can establish the linear convergence of the algorithm under more practical assumptions compared with the linearly convergent derivative-free algorithm recently proposed by Mangasarian and Solodov.