求解非光滑鞍点问题的黄金比率原始对偶算法

数学物理学报 ›› 2024, Vol. 44 ›› Issue (4): 1080-1091.

求解非光滑鞍点问题的黄金比率原始对偶算法

聂佳琳(),龙宪军^*()

重庆工商大学数学与统计学院重庆 400067

收稿日期:2023-06-05 修回日期:2024-03-25 出版日期:2024-08-26 发布日期:2024-07-26
通讯作者: *龙宪军, E-mail: xianjunlong@ctbu.edu.cn
作者简介:聂佳琳, E-mail: niejialin00@163.com
基金资助:
国家自然科学基金(11471059);重庆市自然科学基金(cstc2021jcyj-msxmX0721);重庆市研究生导师团队建设项目(yds223010);重庆市研究生创新型科研项目(CYS240567);重庆工商大学团队项目(ZDPTTD201908)

A Golden Ratio Primal-Dual Algorithm for a Class of Nonsmooth Saddle Point Problems

Nie Jialin(),Long Xianjun^*()

School of Mathematics and Statistics, Chongqing Technology and Business University, Chongqing 400067

Received:2023-06-05 Revised:2024-03-25 Online:2024-08-26 Published:2024-07-26
Supported by:
NSFC(11471059);NSF of Chongqing(cstc2021jcyj-msxmX0721);Team Building Project for Graduate Tutors in Chongqing(yds223010);Innovation Project for Graduate Students of Chongqing(CYS240567);Project of Chongqing Technology and Business University(ZDPTTD201908)

摘要/Abstract

摘要：

该文提出了一类新的黄金比率原始对偶算法求解非光滑鞍点问题, 该算法是完全可分裂的. 在一定的假设下, 证明了由算法迭代产生的序列收敛到问题的解, 同时证明了 $ O(\frac{1}{N}) $ 遍历收敛率. 数值实验表明该文提出的算法比 Zhu, Liu 和 Tran-Ding 文中的算法有更少的迭代步数和计算机耗时.

关键词: 鞍点问题, 黄金比率, 原始对偶算法, 收敛性, 遍历收敛率

Abstract:

In this paper, we present a new golden ratio primal-dual algorithm to solve the nonsmooth saddle point problems, which is full-splitting.Under some appropriate conditions, we prove the sequence generated by the algorithm iteration converges to the solution of the problem, as well as an $ O(1/N) $ ergodic convergence rate result. Finally, with comparisons to Zhu, Liu and Tran-Ding's algorithms, we give some numerical experiments to show the less iterate numbers and CPU time of the proposed method.

Key words: Saddle point problems, Golden ratio, Primal-dual algorithm, Iterate convergence, Ergodic convergence

中图分类号:

O224

聂佳琳, 龙宪军. 求解非光滑鞍点问题的黄金比率原始对偶算法[J]. 数学物理学报, 2024, 44(4): 1080-1091.

Nie Jialin, Long Xianjun. A Golden Ratio Primal-Dual Algorithm for a Class of Nonsmooth Saddle Point Problems[J]. Acta mathematica scientia,Series A, 2024, 44(4): 1080-1091.

图/表 11

表1

表2

表3

表4

表5

表6

图1

图2

图3

图4

参考文献 14

[1]	Bauschke H H, Combettes P. Convex Analysis and Monotone Operators Theory in Hilbert Spaces. New York: Springer-Verlag, 2020
[2]	Chambolle A, Pock T. A first-order primal-dual algorithm for convex problems with applications to imaging. J Math Imaging Vis, 2011, 40: 120-145
[3]	Combettes P, Pesquet J C. Proximal splitting methods in signal processing// Bauschke H, Burachik R, Combetles P, et al. Fixed-Point Algorithms for Inverse Problems in Science and Engineering. New York: Springer-Verlag, 2011: 185-212
[4]	Uzawa H. Iterative methods for concave programming// Arrow K J, Hurwicz L, Uzawa H, eds. Studies in Linear and Nonlinear Programming. Stanford, CA: Stanford University Press, 1958, 6: 154-165
[5]	Esser E, Zhang X, Chan T F. A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J Imaging Sci, 2010, 3: 1015-1046
[6]	He B, You Y, Yuan X. On the convergence of primal-dual hybrid gradient algorithm. SIAM J Imaging Sci, 2014, 7(4): 2526-2537
[7]	Chambolle A, Pock T. On the ergodic convergence rates of a first-order primal-dual algorithm. Math Program, 2016, 159(1): 253-287
[8]	Condat L. A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J Optim Theory Appl, 2013, 158(2): 460-479
[9]	Malitsky Y. Golden ratio algorithms for variational inequalities. Math Program, 2020, 184(1): 383-410
[10]	Xu Y. Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming. Math Program, 2021, 185: 89-117
[11]	周丹青, 常小凯, 杨俊峰. 一类新的黄金比率原始对偶算法. 高等学校计算数学学报, 2022, 44: 97-106
	Zhou D Q, Chang X K, Yang J F. A new Golden ratio primal-dual algorithm. Numerical Math A J Chinese Univ, 2022, 44: 97-106
[12]	Zhu Y, Liu D, Tran-Ding Q. New primal-dual algorithms for a class of nonsmooth and nonlinear convex-concave minimax problems. SIAM J Optim, 2022, 32(4): 2580-2611
[13]	Hamedani E Y, Aybat N S. A primal-dual algorithm with line search for general convex-concave saddle point problems. SIAM J Optim, 2021, 31: 1299-1329
[14]	Rockafellar R, Wets R. Variational Analysis. Berlin: Springer, 2004

[1]	马小军, 陈富, 贾芝福. 基于非 Lipschitz 步长策略的临近分裂可行问题的强收敛性研究[J]. 数学物理学报, 2024, 44(4): 1052-1065.
[2]	简金宝, 代钰, 尹江华. 分裂可行性问题的一个惯性共轭梯度投影法[J]. 数学物理学报, 2024, 44(4): 1066-1079.
[3]	张潇, 张宏武. 分数阶椭圆方程反边值问题的分数 Tikhonov 正则化方法[J]. 数学物理学报, 2024, 44(4): 978-993.
[4]	蔡宇, 周光辉. 一种 WYL 型谱共轭梯度法的全局收敛性[J]. 数学物理学报, 2024, 44(1): 173-184.
[5]	简金宝,林惠,马国栋. 大规模非凸不可分优化问题的分裂序列二次规划算法[J]. 数学物理学报, 2023, 43(4): 1284-1296.
[6]	于一康,牛晶. 一类椭圆型界面问题的数值算法[J]. 数学物理学报, 2023, 43(3): 883-895.
[7]	刘鹏杰, 吴彦强, 邵枫, 张艳, 邵虎. 两个带重启方向的改进 HS 型共轭梯度法[J]. 数学物理学报, 2023, 43(2): 570-580.
[8]	谢亚君,马昌凤. 源于自由边值离散的弱非线性互补问题的m+1阶收敛性算法[J]. 数学物理学报, 2022, 42(5): 1506-1516.
[9]	许文丁,钟婷. 非光滑牛顿算法的收敛性[J]. 数学物理学报, 2022, 42(5): 1537-1550.
[10]	黄媛,支越,康彤,王然,张红. 非线性感应加热问题的全离散有限元方法[J]. 数学物理学报, 2022, 42(4): 1238-1255.
[11]	潘庭葳,贺素香. 双重稀疏约束优化问题的一种贪婪单纯形算法[J]. 数学物理学报, 2022, 42(3): 920-933.
[12]	马昌凤,马飞洋. H-矩阵非线性互补问题基于模的矩阵分裂迭代法改进的收敛性定理[J]. 数学物理学报, 2022, 42(2): 583-593.
[13]	袁功林,吴宇伦,PhamHongtruong. 基于非单调线搜索的HS-DY形共轭梯度方法及在图像恢复中的应用[J]. 数学物理学报, 2022, 42(2): 605-620.
[14]	张宏武. 一类半线性椭圆方程柯西问题的正则化方法[J]. 数学物理学报, 2022, 42(1): 45-57.
[15]	杨晓侠,张厚超. Extended Fisher-Kolmogorov方程的间断有限元分析[J]. 数学物理学报, 2021, 41(6): 1880-1896.