Multiplier Methods For Complementarity Problems

In this dissertation, a theoretical framework of a class of new Lagrangian multiplier methods for complementarity problems(CPs) and mixed complementarity problems(MCPs) is established. By introducing the Lagrangians for the systems of nonsmooth equations being equivalent to CPs and MCPs, some new smooth merit functions containing multiplier parameters are constructed. By means of adjusting the multiplier parameters, the difficulties of intrinsic non-smoothness in the problems are overcome. Thus, the method provides a new way to solve the CPs and MCPs. Several new algorithms for solving CPs and MCPs are presented, the global convergence and local superlinear or quadratic convergence results of the algorithms are proved under weaker assumptions. Extensive numerical experiments indicate that the algorithms are efficient and promising. In particular, for some typical test problems from the MCPLIB, the algorithms are more efficient than other existing algorithms appeared in the literatures.1. For linear complementarity problems(LCPs), a new smooth merit function is constructed, the linearity of LCP is well preserved as the piecewise quadratic convex property of it. By using the merit function a new Lagrangian multiplier method is proposed. Global convergence is proved for LCP with P0-matrix when the solution set is nonempty and bounded. For LCP with P-matrix, the finite termination property is obtained without using the hybrid switch technique or other additional step, at each iteration of our algorithm only a Newton equation needs to be solved.2. For nonlinear complementarity problems(NCPs) a new damped Newton-type method is proposed. Although the merit function introduced here is the sum of squares of overdetermined equations, by using the special structure of it, we successfully form the Newton equation by avoiding the product of Jacobi matrices and using only the Jacobi matrix of the function defining NCP. Two kinds of Newton equations are presented and two different simple adjusting strategies of multiplier parameters are provided. For P0 -functions the global convergence is obtained under the condition that the solution set of NCP is nonempty and bounded which is weaker than those previously used in the literatures, such as the problem is monotone with a feasible interior point or the function is a PQ + R0-function. And the local superlinear or quadratic convergence rate is proved when the solution is R-regular.3. For mixed complementarity problems, through the median function, a new Lagrangian multiplier method is presented. For P0 -functions the global convergence is obtained when the feasible region is bounded. The local superlinear or quadratic convergence rate is also obtained under the condition that the solution is .R-regular.4. For NCPs and MCPs, by eliminating the multiplier parameters from above merit functions, some new simple smooth merit functions without any parameters are obtained respectively. Forthe P0-function any stationary points of the merit functions are the solution of the problems. The merit functions possess good differentiable properties like that of the famous Fischer-Burmeister function and have better coercive property. For the linear problem, the linearity of the problem is also well preserved in the merit functions. The global convergence, local superlinear or quadratic convergence and finite convergence for linear problems of the proposed algorithms are also obtained under conditions as above or even weaker.