• • 上一篇    

求解随机混合变分不等式问题的黄金分割算法

贺月红, 杨澈洲, 龙宪军   

  1. 重庆工商大学数学与统计学院, 重庆 400067
  • 收稿日期:2022-01-18 修回日期:2022-03-31 发布日期:2022-08-31
  • 通讯作者: 龙宪军,Email:xianjunlong@ctbu.edu.cn.
  • 基金资助:
    重庆市自然科学基金(cstc2021jcyj-msxmX0721,cstc2018-jcyjAX0119),重庆市教育委员会科学技术研究重点项目(KJZD-K201900801),重庆市研究生创新型科研项目(CYS22629)资助课题.

贺月红, 杨澈洲, 龙宪军. 求解随机混合变分不等式问题的黄金分割算法[J]. 系统科学与数学, 2022, 42(7): 1837-1850.

HE Yuehong, YANG Chezhou, LONG Xianjun. A Golden Ratio Algorithm for Stochastic Mixed Variational Inequalities[J]. Journal of Systems Science and Mathematical Sciences, 2022, 42(7): 1837-1850.

A Golden Ratio Algorithm for Stochastic Mixed Variational Inequalities

HE Yuehong, YANG Chezhou, LONG Xianjun   

  1. College of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067
  • Received:2022-01-18 Revised:2022-03-31 Published:2022-08-31
引入线性搜索准则,提出了一种新的黄金分割算法求解随机混合变分不等式问题.在不依赖$F$单调性的条件下,通过构造限制价值函数获得了算法的遍历收敛率和oracle复杂度.数值实验结果显示了算法的有效性.最后给出了算法在随机纳什-古诺博弈问题中的应用.
In this paper, we introduce a golden ratio algorithm with line search for solving the stochastic mixed variational inequality problem. Without the assumption of the monotonicity of $F$, we obtain some results related to the ergodic convergence and the oracle complexity of the proposed algorithm via the restricted merit function. We give some numerical experiments to show the efficiency of the algorithm. Finally, we give an application of the algorithm with respect to the stochastic Nash-Cournot game problem.

MR(2010)主题分类: 

()
[1] Facchinei F, Pang J S.Finite-Dimensional Variational Inequalities and Complementarity Problems.New York:Springer, 2003.
[2] Bauschke H H, Combettes P L.Convex Analysis and Monotone Operator Theory in Hilbert Spaces.New York:Springer-Verlag, 2011.
[3] Zhong R Y, Huang N J.Stability analysis for minty mixed variational inequality in reflexive banach spaces.Journal of Optimization Theory and Applications, 2010, 147(3):454-472.
[4] Grad S M, Lara F.Solving mixed variational inequalities beyond convexity.Journal of Optimization Theory and Applications, 2021, 190(2):565-580.
[5] Tang G J, Wan Z P, Huang N J.Strong convergence of a projection-type method for mixed variational inequalities in Hilbert spaces.Numerical Functional Analysis and Optimization, 2018, 39(11):1103-1119.
[6] Malitsky Y.Golden ratio algorithms for variational inequalities.Mathematical Programming, 2020, 184:383-410.
[7] Chen L, Lin G H, Yang X M.Expected residual minimization method for stochastic mixed variational inequality problems.Pacific Journal of Optimization, 2018, 14:703-722.
[8] Chen L, Lin G H, Yang X M.Sample average approximation method based on regularized gap function for stochastic mixed variational inequality problems.Journal of Nonlinear and Convex Analysis, 2019, 20:149-164.
[9] Lin G H, Chen X, Fukushima M.New restricted NCP functions and their applications to stochastic NCP and stochastic MPEC.Optimization, 2007, 56(5-6):641-653.
[10] Hieu D V, Cho Y J, Xiao Y B.Golden ratio algorithms with new stepsize rules for variational inequalities.Mathematical Methods in the Applied Sciences, 2019, 42(18):6067-6082.
[11] Yousefian F, Nedić A, Shanbhag U V.On smoothing, regularization, and averaging in stochastic approximation methods for stochastic variational inequality problems.Mathematical Programming, 2017, 165(1):391-431.
[12] Yousefian F, Nedić A, Shanbhag U V.Self-tuned stochastic approximation schemes for nonLipschitzian stochastic multi-user optimization and Nash games.IEEE Transactions on Automatic Control, 2016, 61(7):1753-1766.
[13] Yang Z P, Zhang J, Zhu X, et al.Infeasible interior-point algorithms based on sampling average approximations for a class of stochastic complementarity problems and their applications.Journal of Computational and Applied Mathematics, 2019, 352:382-400.
[14] Shanbhag U V.Stochastic variational inequality problems:Applications, analysis, and algorithms.INFORMS Tutorials in Operations Research, 2013, 71-107.
[15] Iusem A N, Jofré A, Oliveira R I, et al.Variance-based extragradient methods with line search for stochastic variational inequalities.SIAM Journal on Optimization, 2019, 29(1):175-206.
[16] Bot R I, Mertikopoulos P, Staudigl M, et al.Minibatch forward-backward-forward methods for solving stochastic variational inequalities.Stochastic Systems, 2021, 11:112-139.
[17] Shapiro A, Dentcheva D, Ruszczynski A.Lectures on Stochastic Programming:Modeling and Theory.Philadelphia:SIAM-Society for Industrial and Applied Mathematics, 2009.
[18] Lei J L, Shanbhag U V.Distributed variable sample-size gradient-response and best-response schemes for stochastic Nash games over graphs.https://arxiv.org/abs/1811.11246, 2018.
[19] Robbins H, Monro S.A stochastic approximation method.The Annals of Mathematical Statistics, 1951, 22:400-407.
[20] Jiang H Y, Xu H F.Stochastic approximation approaches to the stochastic variational inequality problem.IEEE Transactions on Automatic Control, 2008, 53(6):1462-1475.
[21] Yang Z P, Lin G H.Two fast variance-reduced proximal gradient algorithms for SMVIPsstochastic mixed variational inequality problems with suitable applications to stochastic network games and traffic assignment problems.Journal of Computational and Applied Mathematics, 2022, 408:114132.
[22] Yang Z P, Lin G H.Variance-based single-call proximal extragradient algorithms for stochastic mixed variational inequalities.Journal of Optimization Theory and Applications, 2021, 190:393-427.
[1] 郑莲. 解拟变分不等式的超平面投影算法[J]. 系统科学与数学, 2013, 33(5): 579-584.
[2] 迟晓妮;刘三阳. 二次锥规划的预估-校正光滑方法[J]. 系统科学与数学, 2009, 29(4): 547-554.
阅读次数
全文


摘要