Some Research On Derivative-free Descent Method And Homotopy Method For Nonlinear Complementarity Problems

In 1964, Cottle firstly presented nonlinear complementarity problems (NCP) in his PHD's article. In 1966, Hartman and Stampacchia related nonlinear complementarity problems (NCP) with variable inequality problems (VIP). From the end of 70's and the beginning of 80's, researches about nonlinear complementarity problems have been developed rapidly.Nonlinear complementarity problems have many applications in a lot of fields, such as mathematical programming, economics equilibrium models and games theory, and so on([10], [16],[24] etc).In this article, we consider the methods for solving nonlinear complementarity problems from two aspects: one is the equivalent formulation of minimization, the other is the equivalence formulation of equation. To the former, we give a new derivative-free descent algorithm based on constrained minimization formulation. To the later, we construct a new homotopy equation and give its algorithm. The whole article is organized as follows.In chapter 1, we introduce the origin of complementarity and definitions of kinds of complementarity problems. Moreover, we present some definitions and lemmas which are needed later in our article.In chapter 2, we discuss the method for solving nonlinear complementarity problems with the equivalent formulation of minimization based on merit function. With merit function, the origin problem can be conformed to unconstrained or constrained minimization problems. There have been many study about the unconstrained equivalent formulation. Many algorithms and theories have been constituted about this kind of formulation. But to the constrained equivalent formulation, there is no corresponding algorithm. In this chapter, we consider the method of constrained equivalent formulation. We use the merit function based on the restrained NCP function and convert the origin problem NCP(F) to minimization problem which constrained on Rn+. We constitute the corresponding derivative-free descent algorithm.After we proved the well-definition and global convergence of our derivative-free descent algorithm, we compare our algorithm with some existent derivative-free descent algorithms based on unconstrained minimization formulation. All the numerical simulations show thatour algorithm is predominant on iterative times over other algorithms. Moreover, our algorithm represent well adaptive capacity on the change of starting point and increase of dimensions.In chapter 3, we discuss the method for solving nonlinear complementarity problems with the equivalent formulation of equation. Firstly, we summarize the main methods about this kind of formulation and make some numerical simulations. Secondly, we discuss the homotopy method for solving nonlinear complementarity problems. Through constituting appropriate homotopy equation, we convert NCP(F) to solving the homotopy equation. Without assumption of regular or non-singularity for VF(r) (which is the Jacobian of F(x)), we prove that the homotopy equation has a bounded solution curve starting from (w(0), 1), and its end point is the solution of NCP(F). Finally, we constitute a homotopy algorithm and the pass-following method for solving the differential equation in the homotopy algorithm. The example also shows the validity of our homotopy method.In chapter 4, we summarize the whole article and present some researching expectation.