Further Study On Beformulation Methods For Solving Complementarity Problems

The complementarity problem (denoted by CP) is an important branch of Operations Research, which has been widely applied to many practical problems. At present, many numerical solution methods for solving the CP have been proposed in the literature, where the reformulation method based on some reformulation function has shown to have great superiority, both in theory and in the numerical calculation. This paper will further study three kinds of reformulation methods for solving the CP.Firstly, based on the Hu-Huang-Chen generalized complementarity func-tion, we propose a class of symmetrically disturbed functions. New constructed functions have better properties than the Hu-Huang-Chen complementarity function. Based on the new functions and the corresponding semi-smooth re-formulation for the CP, this paper investigates a non-monotone semi-smooth Newton algorithm for solving the CP. Specially, under suitable assumptions, we show that the algorithm has the global convergence and local superlinear (quadratic) convergence. The tested numerical results for problems from MC-PLIB are compared with those reported in the literature. The investigated algorithm not only can calculate some examples which can not be calculated in the corresponding literature, but also shows fewer iterations, short CPU time, and high precision, etc. These show that the algorithm is effective.Secondly, we propose a generalized class of smoothing functions, which contains many existing smooth functions as the special cases. Based on the functions and the corresponding smooth reformulation for the CP, this paper investigates a non-interior continuation algorithm for solving the CP. The in-vestigated algorithm is a modified version of Huang algorithm, but it has some bigger superiority than Huang algorithm. Specially, under suitable assump-tions, we have proved that the algorithm has global linear convergence and local quadratic convergence. The problems in MCPLIB have been tested, and the numerical testings shows that the modified algorithm is effective.Finally, based on a generalized penalty complementarity function and the corresponding merit function for the CP, Lu-Huang-Huand proposed a Derivative-Free descent algorithm for the CP and showed the global conver-gence of the algorithm, but no the result on the convergence rate of the method was reported. Under the suitable assumptions, we show in this paper that the iterative sequence generated by the algorithm is globally R-linearly convergent and the corresponding sequence of the merit function is globally Q-linearly convergent.