次梯度外梯度算法求解随机变分不等式
|
摘要
确定性变分不等式已经有了较为完善的理论和数值方法。受次梯度外梯度算法的启发,考虑将其推广到随机变分不等式中。由于随机因素的出现,确定性的数值方法不能直接用来求解随机变分不等式。为此,结合处理随机优化常用的随机逼近方法,提出采用基于次梯度外梯度的随机逼近方法来求解随机变分不等式,即每次迭代抽取一个样本点,用样本函数去代替期望值函数,同时将外梯度算法中的第二步投影改投在含有可行集的一个半空间上,新的迭代点为第k步和矫正步的一个凸组合。该法采取随机逼近方法处理随机问题,并且当投影难以计算的时候,修改第二步投影在半空间上以此来减少计算的代价,新的迭代点充分利用了已知点的信息,使得算法迭代快速有效。在适当的假设下,当函数是伪单调的时候证明了去全局收敛性,并给出了初步的数值试验来证明该算法的可行性。
The deterministic variational inequality has a relatively complete theoretical and numerical method. Inspired by the subgradient extragradient algorithm of deterministic variational inequality,it is considered to be generalized to stochastic variational inequality. Due to the emergence of random factors,deterministic numerical methods cannot be directly applied to solve stochastic variational inequalities. To solve this problem,a stochastic approximation method based on subgradient extragradient is proposed to solve stochastic variational inequality,which is to extract one sample point per iteration,replace the expected value function with the sample function. The second step projection in the algorithm is cast on a half space containing the feasible set,and the new iteration point is a convex combination of the kth step and the corrected step. The algorithm adopts stochastic approximation method to deal with the random problem,and when the projection is difficult to calculate,modifying the second step projection in half space will reduce the cost of calculation. The new iteration point makes full use of the information of known points,making the algorithm iteratively fast. Under the proper assumption,when the function is pseudomonotone,the global convergence is proved,and the preliminary numerical experiments are given to prove the feasibility of the algorithm.
The deterministic variational inequality has a relatively complete theoretical and numerical method. Inspired by the subgradient extragradient algorithm of deterministic variational inequality,it is considered to be generalized to stochastic variational inequality. Due to the emergence of random factors,deterministic numerical methods cannot be directly applied to solve stochastic variational inequalities. To solve this problem,a stochastic approximation method based on subgradient extragradient is proposed to solve stochastic variational inequality,which is to extract one sample point per iteration,replace the expected value function with the sample function. The second step projection in the algorithm is cast on a half space containing the feasible set,and the new iteration point is a convex combination of the kth step and the corrected step. The algorithm adopts stochastic approximation method to deal with the random problem,and when the projection is difficult to calculate,modifying the second step projection in half space will reduce the cost of calculation. The new iteration point makes full use of the information of known points,making the algorithm iteratively fast. Under the proper assumption,when the function is pseudomonotone,the global convergence is proved,and the preliminary numerical experiments are given to prove the feasibility of the algorithm.
引文
[1]FACCHINEI F,PANG J S.Finite-Dimensional variational inequalities and complementarity problems[M].Springer,New York,2003.
[2]FERRIS M C,PANG J S.Engineering and economic applications of complementarity problems[J].Siam Review,1997,39(4):669-713.
[3]XU H.Sample average approximation methods for a class of stochastic variational inequality problems[J].Asia-Pacific Journal of Operational Research,2010,27(1):103-119.
[4]WANG M Z,LIN G H,GAO Y L,et al.Sample average approximation method for a class of stochastic variational inequality problems[J].Journal of Systems Science and Complexity,2011,24(6):1143-1153.
[5]ROBBINS H,MONRO S.A stochastic approximation method[J].Annals of mathematical statistics,1951,22(3):400-407.
[6]JAMES C,SPAL L.Introduction to stochastic search and optimization:estimation,simulation,and control[M].New York:Wiley-Interscience,2003:368-369.
[7]ROCKAFELLAR R T,SUN J.Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging[J].Mathematical Programming,2018:1-19.doi.org/10.1007/s10107-018-1251-y.
[8]JIANG H,XU H.Stochastic approximation approaches to the stochastic variational inequality problem[J].IEEE Transactions on Automatic Control,2008,53(6):1462-1475.
[9]KOSHAL J,NEDIC 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.
[10]YOUSEFIAN F,NEDIA,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.
[11]KANNAN A,SHANBHAG U V.The pseudomonotone stochastic variational inequality problem:Analytical statements and stochastic extragradient schemes[C]//American Control Conference(ACC),IEEE,2014:2930-2935.
[12]IUSEM A N,JOFRE 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.
[13]IUSEM A N,JOFRE A,OLIVEIRA R,et al.Variancebased stochastic extragradient methods with line search for stochastic variational inequalities[J].SIAM Journal on Optimization,2017.DOI:10.1137/17M114479.
[14]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.
[15]LOPEZ G,MARTIN V,XU H K.Perturbation techniques for nonexpansive mappings with applications[J].Nonlinear Analysis Real World Applications,2009,10(4):2369-2383.
[16]ROBBINS H,SIEGMUND D.A Convergence theorem for non negative almost supermartingales and some applications[J].Optimizing Methods in Statistics,1971:233-257.DOI:10.1007/978-1-4612-5110-1_10.
[2]FERRIS M C,PANG J S.Engineering and economic applications of complementarity problems[J].Siam Review,1997,39(4):669-713.
[3]XU H.Sample average approximation methods for a class of stochastic variational inequality problems[J].Asia-Pacific Journal of Operational Research,2010,27(1):103-119.
[4]WANG M Z,LIN G H,GAO Y L,et al.Sample average approximation method for a class of stochastic variational inequality problems[J].Journal of Systems Science and Complexity,2011,24(6):1143-1153.
[5]ROBBINS H,MONRO S.A stochastic approximation method[J].Annals of mathematical statistics,1951,22(3):400-407.
[6]JAMES C,SPAL L.Introduction to stochastic search and optimization:estimation,simulation,and control[M].New York:Wiley-Interscience,2003:368-369.
[7]ROCKAFELLAR R T,SUN J.Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging[J].Mathematical Programming,2018:1-19.doi.org/10.1007/s10107-018-1251-y.
[8]JIANG H,XU H.Stochastic approximation approaches to the stochastic variational inequality problem[J].IEEE Transactions on Automatic Control,2008,53(6):1462-1475.
[9]KOSHAL J,NEDIC 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.
[10]YOUSEFIAN F,NEDIA,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.
[11]KANNAN A,SHANBHAG U V.The pseudomonotone stochastic variational inequality problem:Analytical statements and stochastic extragradient schemes[C]//American Control Conference(ACC),IEEE,2014:2930-2935.
[12]IUSEM A N,JOFRE 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.
[13]IUSEM A N,JOFRE A,OLIVEIRA R,et al.Variancebased stochastic extragradient methods with line search for stochastic variational inequalities[J].SIAM Journal on Optimization,2017.DOI:10.1137/17M114479.
[14]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.
[15]LOPEZ G,MARTIN V,XU H K.Perturbation techniques for nonexpansive mappings with applications[J].Nonlinear Analysis Real World Applications,2009,10(4):2369-2383.
[16]ROBBINS H,SIEGMUND D.A Convergence theorem for non negative almost supermartingales and some applications[J].Optimizing Methods in Statistics,1971:233-257.DOI:10.1007/978-1-4612-5110-1_10.