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.