A Modified Smoothing Newton Method For Solving The Complementarity Problem

Complementarity problem was first proposed in 1963.Since then it has been the hot spot in the research of mathematical programming. Also many algorithms have been proposed.With the idea of smoothing Newton method, we propose a new class of smoothing Newton methods for the nonlinear complementarity problem based on a class of special functions. In this paper, complementarity problem is converted into a series of smoothing nonlinear equations and a modified smoothing Newton algorithm is used to solve the equations. We use Newton direction and Gradient direction together in the algorithm which guarantees that our method is globally convergent. Also using another smoothing function, we reformulate the generalized nonlinear complementarity problems defined on a polyhedral cone as a system of smoothing equations and a smooth unconstrained optimization problem. Theoretical results that relate the stationary points of the merit function to the solution of the generalized nonlinear complementarity problems are presented, we use the modified smoothing Newton algorithm in generalized nonlinear complementarity problems, under mild hypothesis, a global convergence is proved.The paper contains four parts. In the first chapter, the application back ground and the main algorithms of the complementarity problems is introduced. In Chapter 2, some basic definitions and theories of complementarity problems are introduced. The 3rd chapter is the most important part of this paper, in which a modified smoothing Newton method is detailed; also the global convergence is established for the method. In the 4th chapter, we use the modified smoothing Newton algorithm in generalized nonlinear complementarity problems. In the last chapter, we conclude the paper.