Stochastic Approximation Algorithms For Stochastic Variational Inequality Problems

Variational inequality theory is an important branch of operational research,which has been widely used in economic and finance,engineering management,traffic network and optimal control.However,many practical problems affected by uncertain factors can be transformed into the variational inequality model which includes randomness.In this thesis,the expected model of stochastic variational inequality problems is investigated.By the line search criterias,some novel algorithms with convergence analysis and numerical experiments are also investigated.The main research work of this thesis are summarized as follows:A stochstic approximation backward-forward algorithm is presented for solving stochastic variational inequality problems.The new algorithm uses the line search criteria to avoid the calculation of the Lipschitz constant,and a convex combination technique is applied to update the iteration points,which may bring faster convergence speed of the algorithm.Under the condition of Minty variational inequality,the sequence generated by the proposed algorithm converges almost surely to the solution of the original problem,and the sublinear convergence rate as well as the iteration complexity of the algorithm are established.Finally,numerical experiments results show that the new algorithm is feasible and effective.To further improve the computational efficiency of the algorithm,a variance reduced subgradient gradient algorithm with new line search is given for solving stochastic variational inequality problems.By designing new line search criteria,this algorithm only requires one oracle error at each iteration,and does not rely on the Lipschitz constant.Then,the convergence,sublinear convergence rate and complexities of the algorithm are obtained under Minty variational inequality.Besides,the linear convergence rate of the algorithm is also obtained with the assumptions of strongly Minty variational inequality and the bound condition,respectively.Numerical results indicate that the new algorithm has certain advantages in computational efficiency.For stochastic mixed variational inequality problems,a variance reduced proximal backward-forward algorithm with line search is proposed.The proposed algorithm only requires the generalized monotonity and there is no restriction on the Lipschitz constant,while other similar methods require the mapping to be monotone and a known Lipschitz constant.Then,the convergence,sublinear convergence rate and complexities of the algorithm are analyzed under mild assumptions.In addition,the effectiveness and superiority of the new algorithm are verified by numerical experiments,and it is applied to solve the stochastic Nash-Cournot game problem.