次梯度外梯度方法求解随机变分不等式
|
摘要
随机变分不等式在供应链网络、交通运输和博弈论中具有广泛的应用。提出基于次梯度外梯度的随机逼近方法求解随机变分不等式,将矫正步的投影改投在半空间,以此来减少计算投影的代价。在适当的假设下,证明了所提出的算法具有全局收敛性。
Stochastic variational inequalities have a wide range of applications in supply chain networks,transportation and game theory. In this paper, the subgradient extragradient algorithm is proposed to solve the stochastic variational inequality, and the projection of the correction step is changed to the half space to reduce the cost of projection calculation. Under appropriate assumptions, we prove that the proposed algorithm has global convergence.
Stochastic variational inequalities have a wide range of applications in supply chain networks,transportation and game theory. In this paper, the subgradient extragradient algorithm is proposed to solve the stochastic variational inequality, and the projection of the correction step is changed to the half space to reduce the cost of projection calculation. Under appropriate assumptions, we prove that the proposed algorithm has global convergence.
引文
[1]Facchinei F,Pang J S.Finite-Dimensional Variational Inequalities and Complementarity Problems[M].New York:Springer,2003.
[2]Ferris M C,Pang J S.Engineering and economic applications of complementarity problems[J].SIAMReview,1997,39(4):669-713.
[3]Jiang H,Xu H.Stochastic approximation approaches to the stochastic variational inequality problem[J].IEEETransactions on Automatic Control,2008,53(6):1462-1475.
[4]Koshal J,Nedi?A,Shanbhag U V.Regularized iterative stochastic approximation methods for stochastic variational inequality problems[J].IEEE Transactions on Automatic Control,2013,58(3):594-609.
[5]Yousefian F,NediéA,Shanbhag U V.On smoothing,regularization,and averaging in stochastic approximation methods for stochastic variational inequality problems[J].Mathematical Programming,2017,165(1):391-431.
[6]Kannan A,Shanbhag U V.The pseudomonotone stochastic variational inequality problem:Analytical statements and stochastic extragradient schemes[C].American Control Conference(ACC),2014.IEEE,2014:2930-2935.
[7]Iusem A N,JofréA,Oliveira R I,et al.Extragradient method with variance reduction for stochastic variational inequalities[J].SIAM Journal on Optimization,2017,27(2):686-724.
[8]Iusem,Alfredo.Variance-based stochastic extragradient methods with linear search for stochastic variational inequalities[J].arXiv preprint arXiv,2017,1703:00262.
[9]Censor Y,Gibali A,Reich S.Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space[J].Optimization,2012,61(9):1119-1132.
[10]Robbins H,Siegmund D.A convergence theorem for non negative almost supermartingales and some applications[J].Optimizing Methods in Statistics,1971(6):233-257.
[2]Ferris M C,Pang J S.Engineering and economic applications of complementarity problems[J].SIAMReview,1997,39(4):669-713.
[3]Jiang H,Xu H.Stochastic approximation approaches to the stochastic variational inequality problem[J].IEEETransactions on Automatic Control,2008,53(6):1462-1475.
[4]Koshal J,Nedi?A,Shanbhag U V.Regularized iterative stochastic approximation methods for stochastic variational inequality problems[J].IEEE Transactions on Automatic Control,2013,58(3):594-609.
[5]Yousefian F,NediéA,Shanbhag U V.On smoothing,regularization,and averaging in stochastic approximation methods for stochastic variational inequality problems[J].Mathematical Programming,2017,165(1):391-431.
[6]Kannan A,Shanbhag U V.The pseudomonotone stochastic variational inequality problem:Analytical statements and stochastic extragradient schemes[C].American Control Conference(ACC),2014.IEEE,2014:2930-2935.
[7]Iusem A N,JofréA,Oliveira R I,et al.Extragradient method with variance reduction for stochastic variational inequalities[J].SIAM Journal on Optimization,2017,27(2):686-724.
[8]Iusem,Alfredo.Variance-based stochastic extragradient methods with linear search for stochastic variational inequalities[J].arXiv preprint arXiv,2017,1703:00262.
[9]Censor Y,Gibali A,Reich S.Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space[J].Optimization,2012,61(9):1119-1132.
[10]Robbins H,Siegmund D.A convergence theorem for non negative almost supermartingales and some applications[J].Optimizing Methods in Statistics,1971(6):233-257.