Research On The Algorithms Of Stochastic Linear Complementarity Problems

The complementarity problem is one of the hot subjects in optimization. It has a wide range of applications in engineering and economics. In a span of four decades, the subject has developed into a very fruitful discipline in the field of mathematical programming. The developments include a rich mathematical theory and a host of effective solution algorithms. Since some elements may involve uncertain data in many practical problems, the stochastic versions of complementarity problems and variational inequality problems have drawn much attention in the recent literature. We cannot generally expect that there exists a vector satisfying all the constraints. Therefore, an important issue in the study of stochastic complementarity problems and stochastic variational inequality problems is to present an appropriate deterministic formulation of the considered problem. And several reformulations of these problems have been presented to obtain reasonable solutions. The study of theories and algorithms of stochastic linear complementarity problems (SLCP) has important reference value to stochastic nonlinear complementarity problems and stochastic variational inequality problems. So we focus on the SLCP.In this thesis, we consider a class of SLCP with finitely many realizations. Firstly, we introduce briefly the developments of the complementarity problems and the research status of SLCP. Then, we analyze the existing reformulations and algorithms of SLCP and present the basic definitions and conclusions needed. By employing the famous Fischer-Burmeister function, we formulate the considered problem as two systems of semismooth equations which were further formulated as constrained minimization problems, respectively. We present the conditions for the solution sets of the constrained minimization problems to be bounded. Then we propose a feasible semismooth Newton method and a partial projected Newton method to solve these constrained minimization problems. The global and local quadratic convergence results of the proposed algorithms are proved under mild conditions. Moreover, numerical results are reported to show our methods are promising. Finally, we analyze the advantages and disadvantages of our algorithms.