Studies On The Algorithms For Some Complementarity Problems

The paper deals with the study of some algorithms for some complementarity problems. Complementarity problems have arosen increasing attention since it was first proposed in1963, and been developed very quickly especially the recent three decades. Many formulations of them were proposed.Since then it has been the hotspot in the research of mathematical programming field and widely used in engineering, economics, physics, finance, optimal control theory mathematical models and equilibrium models arised from traffic transportation. Hence, it is meaningful to stude the efficient numerical methods for solving complementarity problems. Roughly speaking, the study of complementarity problems can be classified into two classes:theory and algorithms. The former is devoted to the existence, uniquess, stability and sensitivity analysis of the solutions, while the later is intended to solve the problemsefficiently, together with the theoretical analysis of the algorithms. The main contents and results are listed as follow.Different formulations of complementarity problems are introduced in Chapter one, alone with various applications in engineering, economics, physics, finance, optimal control theory mathematical models and equilibrium models arised from traffic transportation..Some algorithms for complementarity problems are described. Meanwhile, the thesis work is outlined briefly.Predictor-corrector method was mainly studied on some complementarity problems in Chapter two. A mixed complementarity problem which was equivalent to a variational inequality with equality linear constraints was studied at first. The mixed complementarity problem was equivalent nonlinear system of equations by perfecting Chen-Harker-Kanzow-Smale function Φ(a,b,μ)=a+b-√(a-b)2+4μ2, and Newton method was used to solve the nonlinear system of equations. Andthe concrete step and complexity of the attack algorithm is given under some conditions. A predictor-corrector method was proposed on the upper mixed complementarity problem. The algorithm started with initial interior point to iterate, and the iterative direction and step length were adjusted by solving two nonlinear equations, then new iterative points wrer generated, and it was proved that the complexity of the algorithm iterations was O(√nL). A numerical experiment was done to the first algorithm at last and numerical test showed the algorithm was effective. The power penalty approach to some complementarity problems was mainly studies in Chapter three. A power penalty method for solving linear complementarity problems was proposed since2008. Then, it is extended for solving nonlinear complementarity problems and mixed nonlinear complementarity problems and is proved to be one of efficient algorithms to be applied to solve complementarity problems. The most important characteristic for this algorithm is it posses an exponential convergence rate. At first it was proved that the horizontal linear complementarity problem is equivalent to a mixed linear complementarity problem and by using the equivalent variational inequality reformulation of horizontal linear complementarity problem, it was proved that the rate of the solution to penalty equations converges to that of horizontal linear complementarity problem exponentially as the penalty parameterλâ†'+∞, provided that the matrix is positive definite. On a similar plan, the power penalty approachwas used to a variational inequalities with box constraints, generalized linear complementarity problem, and a generalized bounded nonlinear complementarity problem. A numerical experiment was done to the variational inequalities with box constraints which equals to a special nonlinear mixed complementarity problem at last and the experimental data were in good accordance with the analysis of the algorithm.Finally, the author sums up the research efforts in the thesis and gives prospects of the further research in the fields.