A Non-Interior-Point Smoothing Algorithm For The P_*NCP

Complementarity problems are an important branch in the mathematical programming field, and they have wide applications in many fields such as engineering, economics, traffic equilibrium problem and operations research. Complementarity problems have been developed extensively and there have developed many numerical methods for them. Smoothing algorithm is one of the most effective methods. The main idea of this method as follow: first reformulate the complementarity problem as a non-smooth equation, then approximate the nonsmooth equation by a family of smooth equation involving a smoothing parameter, finally use Newton method to solve the smooth equations.Thesis mainly deals with the non-interior-point smoothing algorithm. In Chapter One, different formulations of complementarity problems are introduced, and their various applications in engineering, economics and operations research are described briefly. Some existing algorithm for complementarity problems are described in Chapter Two. In Chapter Three, the non-interior-point smoothing algorithm for monotone NCP proposed in [30] is extended to solving the P_*NCP, which contains monotone NCP as a special case, and its globally convergence is obtained without any additional condition. Moreover, the solution obtained by the algorithm is proved to be a maximally complementary solution of the P_*NCP.