在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2023, Vol. 40 ›› Issue (3): 366-380.doi: 10.3969/j.issn.1005-3085.2023.03.003

• • 上一篇    下一篇

求解随机变分不等式问题的随机逼近向前–向后算法

贺月红1,  龙宪军1,  唐  平2   

  1. 1. 重庆工商大学数学与统计学院，重庆 400067
    2. 重庆文理学院数学与大数据学院，重庆 402160
  • 收稿日期:2021-05-21 接受日期:2022-09-13 出版日期:2023-06-15 发布日期:2023-08-15
  • 通讯作者: 龙宪军 E-mail: xianjunlong@ctbu.edu.cn
  • 基金资助:
    重庆市自然科学基金 (cstc2021jcyj-msxmX0721; cstc2018jcyjAX0119)；重庆市教育委员会科学技术研究重点项目 (KJZD-K201900801)；重庆市研究生创新型科研项目 (CYS22629; CYS22631)；重庆市研究生导师团队建设项目 (yds223010).

Stochastic Approximation Backward-forward Algorithm for Solving Stochastic Variational Inequality Problems

HE Yuehong1,   LONG Xianjun1,   TANG Ping2   

  1. 1. School of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067
    2. School of Mathematics and Big Data, Chongqing University of Arts and Sciences, Chongqing 402160
  • Received:2021-05-21 Accepted:2022-09-13 Online:2023-06-15 Published:2023-08-15
  • Contact: X. Long. E-mail address: xianjunlong@ctbu.edu.cn
  • Supported by:
    The Natural Science Foundation of Chongqing (cstc2021jcyj-msxmX0721; cstc2018 jcyjAX0119); the Key Science and Technology Research Foundation of Chongqing Education Committee (KJZD-K201900801); the Innovative Project of Chongqing (CYS22629; CYS22631); the Team Building Project for Graduate Tutors in Chongqing (yds223010).

PDF (PC)

133

摘要：

由于其在交通运输、随机博弈和经济均衡等领域中的广泛应用，关于随机变分不等式数值算法的研究受到广泛关注。借助于随机逼近方法，提出了求解随机变分不等式问题的向前–向后线搜索算法，该算法每次迭代只需计算一次到闭凸集上的投影，并且不要求Lipschitz常数信息，从而避免了很多不必要的计算量。在温和的假设下，证明了算法产生的序列几乎处处收敛到随机变分不等式问题的解，以及算法基于自然残差剩余函数的次线性收敛率和迭代复杂度结果。最后，通过数值算例验证了算法的可行性和有效性。

关键词: 随机变分不等式, 向前–向后算法, 随机逼近, 线搜索

Abstract:

Due to its wide application in problems such as transportation, stochastic games and economic equilibrium, the numerical algorithm for stochastic variational inequality has attracted extensive attention. By means of the stochastic approximation method, a forward-backward algorithm with line search for solving stochastic variational inequalities is proposed. At each iteration, the algorithm only needs to calculate one projection onto the closed convex set, and does not require the information about the Lipschitz constant, thus avoiding a lot of unnecessary computation. Under mild assumptions, it is proved that the sequence generated by the algorithm converges almost surely to the solution of the stochastic variational inequality problem. With the help of natural residual function, the results of sublinear convergence rate and the iteration complexity of the algorithm are also obtained. Finally, the feasibility and effectiveness of the algorithm are verified by some numerical examples.

Key words: stochastic variational inequality, backward-forward algorithm, stochastic approximation, line search

中图分类号: