The Smoothing Method For Nonlinear Complementarity Problems

We study the numerical methods for the nonlinear complementarity problem. The nonlinear complementarity problem has many important applications in economics and engineering, and there have developed many numerical methods to solve it and global and local convergence results have also been obtained. In the last years more attention has been devoted to reformulating the nonlinear complementarity problem as a system of nonsmooth equations by using some NCP function.The smoothing trust region method proposed in this paper is an expansion of Yang and Qi's method, it is well-defined for an arbitrary complementarity problem.Compared with line search, trust region methods are more reliable and robust, and more valid in resolving problems. As a class of important methods for the solution of nonsmooth problems, smoothing methods have some favorable advantages. In this paper, by using Fischer-Burmeister function, we reformulate the nonlinear complementarity problem as a system of nonsmooth nonlinear equations and we use Kanzow's smooth approximation function for the Fischer-Burmeister function. By combining trust region method with line search strategy, a smoothing trust region method is proposed. A specific condition is proposed in our algorithm: If this condition is satisfied, we will use the trust region step; Otherwise, we will use the gradient step. We prove that the sequence generated by our algorithm remains in a level set, and under the condition that the level set is compact, there exists at least one accumulation point of the sequence generated by the algorithm is a solution of the nonlinear complementarity problem. If the solution is R-regular, the whole sequence generated by our algorithm converges to an unique point and the convergence rate is 0-superlinear/ Q-quadratic. Numerical results indicate that our algorithm is quite promising.