Research On Algorithms For Stochastic Linear Complementarity Problems

As one of the hot subjects in the optimization research field, complementarity problem plays an important role in many aspects: engineering design, economic equilibrium, transportation problem and game theory, act. In practice, some conditions may effected by many uncertain datas — the weather, the traffic, the demand, and so on. So, stochastic complementarity problems(SCP) have draw increasing attention in the recent optimization research community. Because of the existence of the random elements, there always no vector satisfying all the constrains in general. An common method to study the stochastic complementarity problems is to present an appropriate deterministic reformulation of them, and then propose corresponding algorithms. The study of theories and algorithms of stochastic linear complementarity problems has an important reference value to stochastic complementarity problems. In this paper, we consider a class of stochastic linear complementarity problems(SLCP). The work we have done mainly contains the follows:1. We presented a brief review of the development history of complementarity problems, the basic form of stochastic linear complementarity problems, and several types of formulations for solving SCP. What’s more, the symbolic representation and basic definitions that we needed are given.2. By employing the slack variable and the noted Fischer-Burmeister function, we formulate the SLCP as a kind of constrained minimization problem. Then we presented a semismooth projected Newton method to solve the problem. The global convergence of the method was proved and the numerical result was given.3. To further simplify the above question than mentioned in part 2, we reduce the number of the equations contained in the constrained minimization problem. And the Barzilai-Borwein method was proposed to solve the new question. It performs better in both theoretical and numerical.4. We formulate the SLCP as another kind of constrained minimization problem——expected residual minimization formulation by employing the Fischer-Burmeister function. And then we presented a Barzilai-Borwein method to solve the problem. Finally, we gave some numerical results to demonstrate the effectiveness of the method.