A Method For The Nonlinear Complementarity Problem With Constrained Optimization Reformulation

Nonlinear complementarity problem was put forward in 60's last centuary, but the research on it began from the end of 70's. In these thirty years, complementarity problem has developed into a fruitful subject and it has a lot of applications in economy, engineering and mathematical programming.This dissertation is about the research on the algorithms of nonlinear complementarity problem, and bringing forward a new effective algorithm for solving nonlinear complementarity problem is our objective. So we have not only to proof the rationality and the convergence of the new algorithm, but also to present good numerical results. The headlines of this paper is as follows: First, we give an overview of different algorithms for solving complementarity problem. Through reading a lot of literature, we introduce some popular algorithms presently, including smoothing equation method, nonsmoothing equation method, minimizing method, GLP projection method, interior point method and smoothing Newton method. We list their research results, especially elaborating the basis and the background of minimizing method and smoothing Newton method which are the foundation of following work.Second, we consider the method of constrained minimizing formulation for solving complementarity problem. As we know, the method of transforming the complementarity problem to unconstrained optimization problem has been comparatively grown up. Many algorithms and theories have been constituted about this kind of formulation. However, there is not many study on the constrained minimizing formulation. Our paper starts with this problem, first presents a new class of restricted NCP-functions and gives a new derivative-free descent algorithm based on it. After proving the rationality and the convergence of the new derivative-free algorithm, we compare it to other related algorithms given before. The results show that our new algorithm is effective for solving monotone nonlinear complementarity problem and predominant on iterative numbers.Third, we consider the smoothing newton method for solving complementarity problem. As I know, the paper existing before solves the complementarity problem using given smoothing function with parameter, while our paper extends the smoothing function to a general function and gets a new modified algorithm. We can prove that under some assumptions the modified algorithm preserves the global convergence and fast local convergence of the original algorithm.