单边相对光滑非凸-凹极小极大问题的镜像梯度算法

doi:10.15960/j.cnki.issn.1007-6093.2024.01.002

运筹学学报（中英文） ›› 2024, Vol. 28 ›› Issue (1): 18-28.doi: 10.15960/j.cnki.issn.1007-6093.2024.01.002

单边相对光滑非凸-凹极小极大问题的镜像梯度算法

徐洋¹, 王军霖¹, 徐姿¹^,*()

1. 上海大学理学院数学系, 上海 200444

收稿日期:2021-09-24 出版日期:2024-03-15 发布日期:2024-03-15
通讯作者: 徐姿 E-mail:xuzi@shu.edu.cn
基金资助:
国家自然科学基金(12071279);上海市自然科学基金(20ZR1420600)

A mirror descent gradient ascent algorithm for one side relatively smooth nonconvex-concave minimax optimization problems

Yang XU¹, Junlin WANG¹, Zi XU¹^,*()

1. Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, China

Received:2021-09-24 Online:2024-03-15 Published:2024-03-15
Contact: Zi XU E-mail:xuzi@shu.edu.cn

摘要/Abstract

摘要：

本文提出了一种镜像梯度下降梯度上升算法来求解单边相对光滑的非凸-凹极小极大问题。在算法的每次迭代中, 我们采用镜像梯度下降步来更新相对光滑的变量, 采用梯度上升投影步来更新目标函数中光滑的变量。本文在理论上证明了算法收敛到$\varepsilon$-近似一阶稳定点的迭代复杂度是$\mathcal{O}\left( \varepsilon^{-4} \right)$。

关键词: 非凸-凹极小极大问题, 相对光滑, 镜像梯度法

Abstract:

In this paper, we propose a mirror descent gradient ascent algorithm to solve one side relatively smooth nonconvex-concave minimax optimization problems. At each iteration of the proposed algorithm, a mirror descent step is performed to update the relatively smooth variable, while a gradient ascent projection step is used to update the smooth variable alternately. We also prove that the iteration complexity of the proposed algorithm is $\mathcal{O}\left( \varepsilon ^{-4} \right)$ to achieve an $\varepsilon$-approximate first-order stationary point.

Key words: nonconvex-concave minimax optimization problem, relatively smooth, mirror gradient method

中图分类号:

O221.2

徐洋, 王军霖, 徐姿. 单边相对光滑非凸-凹极小极大问题的镜像梯度算法[J]. 运筹学学报（中英文）, 2024, 28(1): 18-28.

Yang XU, Junlin WANG, Zi XU. A mirror descent gradient ascent algorithm for one side relatively smooth nonconvex-concave minimax optimization problems[J]. Operations Research Transactions, 2024, 28(1): 18-28.

1	Sinha A, Namkoong H, Du C. Certifiable distributional robustness with principled adversarial training[C]//International Conference on Learning Representations, 2018.
2	Goodfellow I , Pouget-Abadie J , Mirza M .Generative adversarial nets[J].Advances in Neural Information Processing Systems,2014,2672-2680.
3	Zhang Y, Xiao L. Stochastic primal-dual coordinate method for regularized empirical risk minimization[C]//International Conference on Machine Learning, 2015: 353-361.
4	Nemirovski A .Prox-method with rate of convergence O(1/$t$) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems[J].SIAM Journal on Optimization,2004,15(1):229-251. doi: 10.1137/S1052623403425629
5	Nesterov Y .Dual extrapolation and its applications to solving variational inequalities and related problems[J].Mathematical Programming,2007,109(2/3):319-344.
6	Lin T, Jin C, Micheal J. Near-optimal algorithms for minimax optimization[C]//Conference on Learning Theory, 2020: 2738-2779.
7	Lu S , Tsaknakis I , Hong M , et al.Hybrid block successive approximation for one-sided non-convex min-max problems: Algorithms and applications[J].IEEE Transactions on Signal Processing,2020,68,3676-3691. doi: 10.1109/TSP.2020.2986363
8	Xu Z , Zhang H , Xu Y , et al.A unified single-loop alternating gradient projection algorithm for nonconvex-concave and convex-nonconcave minimax problems[J].Mathematical Programming,2023,201(1-2):635-706. doi: 10.1007/s10107-022-01919-z
9	Zhang J , Xiao P , Sun R , et al.A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems[J].NeurIPS,2020,33,7377-7389.
10	徐姿, 张慧灵.非凸极小极大问题的优化算法与复杂度分析[J].运筹学学报,2021,25(3):1-13.
11	Tseng P. On accelerated proximal gradient methods for convex-concave optimization[EB/OL]. (2008-05-21)[2021-08-09]. https://www.csie.ntu.edu.tw/b97058/tseng/papers/apgm.pdf.
12	Hou C, Thekumparampil K, Fanti G. Efficient algorithms for federated saddle point optimization[EB/OL]. (2021-02-12)[2021-08-09]. arXiv: 2102.06333.
13	Huang F, Gao S, Heng H. Bregman gradient policy optimization[EB/OL]. (2021-06-23)[2021-08-09]. arXiv: 2106.12112.
14	Lu H , Freund M , Nesterov Y .Relatively-smooth convex optimization by first-order methods and applications[J].SIAM Journal on Optimization,2018,28(1):333-354. doi: 10.1137/16M1099546
15	Ghadimi S , Lan G , Zhang H .Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization[J].Mathematical Programming,2016,155,267-305. doi: 10.1007/s10107-014-0846-1
16	Nesterov Y .Introductory Lectures on Convex Optimization[M].New York: Springer Science & Business Media,2013.
17	Balseiro S R , Lu H , Mirrokni V .The best of many worlds: Dual mirror descent for online allocation problems[J].Operations Research,2023,71(1):101-119. doi: 10.1287/opre.2021.2242
18	Ibrahim M, Konar A, Hong M. Mirror-prox SCA algorithm for multicast beamforming and antenna selection[C]//IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications, 2018.

[1]	王祥丰, 曾尚志, 张进, 周金川. 面向非凸非光滑最优化问题的临近类方法寻找“钝化”局部最优解[J]. 运筹学学报（中英文）, 2026, 30(2): 1-23.
[2]	门彦超, 郦旭东. OWL1范数约束回归模型的快速算法[J]. 运筹学学报（中英文）, 2026, 30(2): 24-44.
[3]	曾静, 向耀, 张文燕. 交通均衡问题的适定性[J]. 运筹学学报（中英文）, 2026, 30(2): 58-68.
[4]	王峰, 杭波, 黄金洲, 徐德刚, 张泽宇, 刘佳谋. 一种基于动态情境感知的旅游路径规划方法[J]. 运筹学学报（中英文）, 2026, 30(2): 69-78.
[5]	吴晓宇, 邵虎, 刘鹏杰, 周金诚. 两个充分下降的RMIL型共轭梯度法及图像去噪应用[J]. 运筹学学报（中英文）, 2026, 30(2): 79-92.
[6]	崔恒鑫, 姜帆. 求解单调变分不等式的非精确邻近点算法与投影算法[J]. 运筹学学报（中英文）, 2026, 30(2): 194-208.
[7]	张雪峰, 彭潇, 陈良育, 杨争峰, 曾振柄. 面向混合整数线性规划问题的智能分支定界算法综述[J]. 运筹学学报（中英文）, 2026, 30(2): 237-270.
[8]	魏佳祯, 边伟. 共识优化算法的研究进展综述[J]. 运筹学学报（中英文）, 2026, 30(1): 1-23.
[9]	周允旭, 姚凡军, 高红伟. 区块链赋能数字化转型: 供应链协同运营策略研究[J]. 运筹学学报（中英文）, 2026, 30(1): 61-74.
[10]	赵弘欣, 孔令臣. 分散化投资组合的优化模型和方法研究[J]. 运筹学学报（中英文）, 2026, 30(1): 75-92.
[11]	孙珂, 王金亭, 王钟彬. 基于“排队等待区域娱乐”的经济效益分析[J]. 运筹学学报（中英文）, 2026, 30(1): 93-107.
[12]	许可, 吉兰萍, 宫华, 刘鹏, 孙文娟. 基于拍卖算法的多代理并行机生产运输协调调度[J]. 运筹学学报（中英文）, 2026, 30(1): 121-136.
[13]	王子琦, 王军霖, 徐姿. 一类非凸-非凹极小极大问题的方差缩减梯度下降上升算法[J]. 运筹学学报（中英文）, 2026, 30(1): 197-206.
[14]	杨金佶, 沈春根, 宇振盛. 关于求解平方根损失函数回归问题的自适应邻近梯度-次梯度算法的收敛性分析[J]. 运筹学学报（中英文）, 2026, 30(1): 217-234.
[15]	孙瑞卿, 张芮, 兰艳, 李伟东. 提前完工总量最大化问题的LPT算法[J]. 运筹学学报（中英文）, 2025, 29(4): 249-254.

单边相对光滑非凸-凹极小极大问题的镜像梯度算法

A mirror descent gradient ascent algorithm for one side relatively smooth nonconvex-concave minimax optimization problems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

相关文章 15

编辑推荐

Metrics

本文评价