Numerical Methods For Solving Stochastic Generalized Linear Complementarity Problems

The complementarity problem is one of the important research topics in optimization which is widely used in the fields of engineering,biological,economy,and it also has made great progress both in the area of theoretical research and algorithm research.In recent years,due to the increasing uncertain random parameters which appear in practical problems,it is necessary to study the stochastic complementarity problems.Because of the uncertainty of parameters,it is not likely to find a common solution that satisfies all the constraints,so how to give a deterministic reformulation of a stochastic complementary problem and design effective algorithms for approximate solution has become an important research topic.With further research,people generalize the stochastic complementarity problems into the stochastic generalized complementarity problems in order to solve more extensive practical problems.The stochastic generalized linear complementarity problem is a generalized linear complementarity problem with random variables and it's closely related to the simple stochastic games.Similarly,due to the existence of random parameters,it is impossible to find a solution that satisfies all the constraints for stochastic generalized linear complementarity problem.Therefore,the idea of studying the reformulations and solution methods of stochastic generalized linear complementarity problems by referring to the research ideas and methods of stochastic linear complementarity problems comes out.This paper researches a class of stochastic generalized linear complementarity problems with discrete random variables.By referring to the research results of complementarity problems and stochastic complementarity problems,the expected value reformulation(EV)is used to reformulate the complementarity constraints with random variables into deterministic constraints.Firstly,the stochastic generalized linear complementarity problem is reformulated as a system of smoothing equations under the smoothing symmetric perturbed Fischer function and a smoothing Newton method with nonmonotone line search is used to solve the smoothing equations.It is proved that the algorithm is globally and locally superlinearly convergent under suitable assumptions.Secondly,the reformulated smoothing equations are transformed into unconstraint minimization problem,and the improved spectral conjugate gradient algorithm with nonmonotone line search is also introduced in this paper.The algorithm is globally convergent under suitable assumptions.Furthermore,the algorithm is R-linearly convergent under some assumptions.Numerical results have proved the validity of our algorithms.