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

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

References

[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
[11]	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]	Yu Dongmei, Liu Dayi. The Levenberg-Marquardt Algorithm for Solving the Generalized Complementarity Problems [J]. Acta mathematica scientia,Series A, 2025, 45(4): 1311-1326.
[2]	Fang Donghui,Wang Junying. Characterizations of Approximate Solution and Approximate Duality for Quasiconvex Programming [J]. Acta mathematica scientia,Series A, 2025, 45(2): 640-652.
[3]	Ran Bo,Sun Xiangkai,Guo Xiaole. On Robust Optimal Solutions for a Class of Uncertain Fractional Polynomial Optimization Problems [J]. Acta mathematica scientia,Series A, 2025, 45(2): 630-639.
[4]	Wang Wujing, Zhu Meiling, Zhang Yongle. A New Projection Algorithm for Solving Quasimonotone Variational Inequality Problems and Fixed Point Problems [J]. Acta mathematica scientia,Series A, 2025, 45(1): 236-255.
[5]	Jing Zhao, Chenzheng Guo. Two-Step Inertial Bregman Proximal Alternating Linearized Minimization Algorithm for Nonconvex and Nonsmooth Problems [J]. Acta mathematica scientia,Series A, 2024, 44(6): 1630-1651.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	Wending Xu,Ting Zhong. The Convergence of Nonsmooth Newton's Method [J]. Acta mathematica scientia,Series A, 2022, 42(5): 1537-1550.
[13]	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.
[14]	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.
[15]	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.

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

RichHTML

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0