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

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

Abstract

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

CLC Number:

O221.2

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.

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.ort.shu.edu.cn/EN/10.15960/j.cnki.issn.1007-6093.2024.01.002

https://www.ort.shu.edu.cn/EN/Y2024/V28/I1/18

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]	WANG Xiangfeng, ZENG Shangzhi, ZHANG Jin, ZHOU Jinchuan. Proximal-based methods can guarantee blunt local minimizer for nonconvex nonsmooth optimization problem [J]. Operations Research Transactions, 2026, 30(2): 1-23.
[2]	MEN Yanchao, LI Xudong. Fast algorithm for OWL1 norm constrained regression model [J]. Operations Research Transactions, 2026, 30(2): 24-44.
[3]	ZENG Jing, XIANG Yao, ZHANG Wenyan. The well-posedness of traffic equilibrium problems [J]. Operations Research Transactions, 2026, 30(2): 58-68.
[4]	WANG Feng, HANG Bo, HUANG Jinzhou, XU Degang, ZHANG Zeyu, LIU Jiamou. Research of touring route planning based on spatio-temporal awareness [J]. Operations Research Transactions, 2026, 30(2): 69-78.
[5]	WU Xiaoyu, SHAO Hu, LIU Pengjie, ZHOU Jincheng. Two RMIL-type conjugate gradient methods with sufficient descent property and applications in image restoration [J]. Operations Research Transactions, 2026, 30(2): 79-92.
[6]	CUI Hengxin, JIANG Fan. Inexact proximal point algorithms and projection methods for monotone variational inequalities [J]. Operations Research Transactions, 2026, 30(2): 194-208.
[7]	ZHANG Xuefeng, PENG Xiao, CHEN Liangyu, YANG Zhengfeng, ZENG Zhenbing. A review of intelligent branch and bound algorithms for mixed integer linear programming problems [J]. Operations Research Transactions, 2026, 30(2): 237-270.
[8]	WEI Jiazhen, BIAN Wei. A survey on research advances in consensus-based optimization algorithm [J]. Operations Research Transactions, 2026, 30(1): 1-23.
[9]	ZHOU Yunxu, YAO Fanjun, GAO Hongwei. Blockchain empowering the digital transformation: Study on the coordination strategies of supply chain [J]. Operations Research Transactions, 2026, 30(1): 61-74.
[10]	ZHAO Hongxin, KONG Lingchen. Research on diversification portfolio optimization model and method [J]. Operations Research Transactions, 2026, 30(1): 75-92.
[11]	SUN Ke, WANG Jinting, WANG Zhongbin. The economics of waiting-area entertainment [J]. Operations Research Transactions, 2026, 30(1): 93-107.
[12]	XU Ke, JI Lanping, GONG Hua, LIU Peng, SUN Wenjuan. A coordinated multi-agent production and transportation scheduling on parallel machines based on auction algorithm [J]. Operations Research Transactions, 2026, 30(1): 121-136.
[13]	WANG Ziqi, WANG Junlin, XU Zi. A variance reduced gradient descent ascent algorithm for a class of nonconvex-nonconcave minimax problems [J]. Operations Research Transactions, 2026, 30(1): 197-206.
[14]	YANG Jinji, SHEN Chungen, YU Zhensheng. Convergence analysis of an adaptive proximal gradient-subgradient algorithm for square-root-loss regression problems [J]. Operations Research Transactions, 2026, 30(1): 217-234.
[15]	Ruiqing SUN, Rui ZHANG, Yan LAN, Weidong LI. LPT algorithm for early work maximization problem [J]. Operations Research Transactions, 2025, 29(4): 249-254.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments