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

Abstract

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

CLC Number:

O224

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.

Trendmd

Figures/Tables 11

References 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]	Wang Ruyu, Zhao Wenling, Song Daojin. The Finite Termination of Feasible Solution Sequence for Optimization and Variational Inequality [J]. Acta mathematica scientia,Series A, 2024, 44(4): 1037-1051.
[2]	Hu Shanshan, He Suxiang. Optimality Conditions for Non-Negative Group Sparse Constrained Optimization Problems [J]. Acta mathematica scientia,Series A, 2024, 44(2): 500-512.
[3]	Huang Jiayi, Sun Xiangkai. Duality Characterizations for a Class of Two-Stage Adjustable Robust Multiobjective Programming [J]. Acta mathematica scientia,Series A, 2024, 44(1): 185-194.
[4]	Li Xulin,He Suxiang,Wang Chuanmei. High Dimensional Random Effects Linear Regression Model Based on Mixed Penalties of SCAD_L$_2$ and SCAD [J]. Acta mathematica scientia,Series A, 2023, 43(4): 1297-1310.
[5]	Zeng Jing,Peng Jiayu. Essential Stability and Hadamard Well-Posedness of Excess Demand Equilibrium Problems [J]. Acta mathematica scientia,Series A, 2023, 43(3): 930-938.
[6]	Caiyun Xiao,Xiangkai Sun. Characterization of the Radius of the Robust Feasibility for a Class of Uncertain Convex Optimization Problems with Polynomial Constraints [J]. Acta mathematica scientia,Series A, 2022, 42(5): 1551-1559.
[7]	Wending Xu,Ting Zhong. The Convergence of Nonsmooth Newton's Method [J]. Acta mathematica scientia,Series A, 2022, 42(5): 1537-1550.
[8]	Yajun Xie,Changfeng Ma. Algorithm with Order m + 1 Convergence for Weakly Nonlinear Complementarity Problems Derived From the Discretization of Free Boundary Problems [J]. Acta mathematica scientia,Series A, 2022, 42(5): 1506-1516.
[9]	Tingwei Pan,Suxiang He. The Greedy Simplex Algorithm for Double Sparsity Constrained Optimization Problems [J]. Acta mathematica scientia,Series A, 2022, 42(3): 920-933.
[10]	Jing Yang,Xianjun Long. A New Projection Algorithm for Solving Pseudo-Monotone Variational Inequality and Fixed Point Problems [J]. Acta mathematica scientia,Series A, 2022, 42(3): 904-919.
[11]	Jiaolang Wang,Donghui Fang. Approximate Optimality Conditions and Mixed Type Duality for a Class of Non-Convex Optimization Problems [J]. Acta mathematica scientia,Series A, 2022, 42(3): 651-660.
[12]	Jing Zeng,Ruiting Hu. Stability of Benson Proper Efficient Solutions for Vector Optimization Problems [J]. Acta mathematica scientia,Series A, 2022, 42(1): 35-44.
[13]	Yuehong He,Xianjun Long. A Inertial Contraction and Projection Algorithm for Pseudomonotone Variational Inequality Problems [J]. Acta mathematica scientia,Series A, 2021, 41(6): 1897-1911.
[14]	Yuying Zhao,Yuzhen Wen. Optimal Investment and Proportional Reinsurance Strategies to Minimize the Probability of Drawdown Under Ambiguity Aversion [J]. Acta mathematica scientia,Series A, 2021, 41(4): 1147-1165.
[15]	Yajun Xie. A Class of Efficient Modified Algorithms Based onHalley-Newton Methods [J]. Acta mathematica scientia,Series A, 2021, 41(4): 1066-1078.

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

RichHTML

PDF (PC)

Abstract

Cite this article

share this article

Figures/Tables 11

References 14

Related Articles 15

Metrics

Comments

Recommended 10