本文针对单调算子的零点问题提出了一种新的预测-校正算法框架。多块可分凸优化问题、鞍点问题等均可转换为零点问题,并利用该算法框架设计算法。该算法框架不仅可以包含松弛的向前向后分裂算法和松弛的Davis-Yin分裂算法,还可以通过选取合适的预测算法和校正矩阵,得到Chang等(2025)中的算法3.1和5.1,从而简化其收敛性证明。
This paper proposes a novel predictor-corrector algorithm framework for monotone inclusion problems. Many classes of problems, such as multi-block separable convex optimization problems and saddle point problems, can be reformulated as monotone inclusions, and algorithms can be designed via the proposed framework. The framework not only encompasses the relaxed forward-backward splitting method and the relaxed Davis-Yin splitting method, but also reproduces Algorithm 3.1 and Algorithm 5.1 in Chang et al (2025) by appropriately selecting the predictor steps and correction matrices, thereby simplifying their convergence analysis.
[1] Zhu M, Chan T. An efficient primal-dual hybrid gradient algorithm for total variation image restoration [R]. CAM Report 08-34. Los Angeles: University of California, 2008.
[2] 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 [J]. SIAM Journal on Imaging Sciences, 2010, 3(4): 1015-1046.
[3] Chambolle A, Pock T. A first-order primal-dual algorithm for convex problems with applications to imaging [J]. Journal of Mathematical Imaging and Vision, 2011, 40(1): 120-145.
[4] Cai X, Han D, Xu L. An improved first-order primal-dual algorithm with a new correction step [J]. Journal of Global Optimization, 2013, 57(4): 1419-1428.
[5] He B, Ma F, Xu S, et al. A generalized primal-dual algorithm with improved convergence condition for saddle point problems [J]. SIAM Journal on Imaging Sciences, 2022, 15(3): 1157-1183.
[6] Martinet B. Régularisation d’inéquations variationnelles par approximations successives [J]. Revue fra?caise d’informatique et de recherche opérationnelle. Série rouge, 1970, 4(R3): 154- 158.
[7] Rockafellar R T. Monotone operators and the proximal point algorithm [J]. SIAM Journal on Control and Optimization, 1976, 14(5): 877-898.
[8] Lions P L, Mercier B. Splitting algorithms for the sum of two nonlinear operators [J]. SIAM Journal on Numerical Analysis, 1979, 16(6): 964-979.
[9] Jia Z, Cai X. A relaxation of the parameter in the forward-backward splitting method [J]. Pacific Journal of Optimization, 2017, 13(4): 665-681.
[10] Chang X, Yang J, Bai J, et al. A primal-dual splitting algorithm with convex combination and larger step sizes for composite monotone inclusion problems [J]. SIAM Journal on Imaging Sciences, 2025, 18(4): 2094-2126.
[11] He B S. PPA-like contraction methods for convex optimization: a framework using variational inequality approach [J]. Journal of the Operations Research Society of China, 2015, 3(4): 391- 420.
[12] Bauschke H H, Combettes P L. Convex analysis and monotone operator theory in Hilbert spaces [M]. Cham: Springer International Publishing, 2017.
[13] Douglas J, Rachford H H. On the numerical solution of heat conduction problems in two and three space variables [J]. Transactions of the American Mathematical Society, 1956, 82(2): 421-439.
[14] Eckstein J, Bertsekas D P. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators [J]. Mathematical Programming, 1992, 55(1): 293- 318.
[15] Bredies K, Sun H. Preconditioned Douglas-Rachford splitting methods for convex-concave saddle-point problems [J]. SIAM Journal on Numerical Analysis, 2015, 53(1): 421-444.
[16] Davis D, Yin W. A three-operator splitting scheme and its optimization applications [J]. SetValued and Variational Analysis, 2017, 25(4): 829-858.
[17] He B, Yuan X. Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective [J]. SIAM Journal on Imaging Sciences, 2012, 5(1): 119-149.
[18] Arrow K J, Hurwicz L, Uzawa H. Studies in linear and non-linear programming [M]. Stanford: Stanford University Press, 1958.
[19] He B, You Y, Yuan X. On the convergence of primal-dual hybrid gradient algorithm [J]. SIAM Journal on Imaging Sciences, 2014, 7(4): 2526-2537.
[20] Korpelevich G M. An extragradient method for finding saddle points and for other problems [J]. Ekonomika i Matematicheskie Metody, 1976, 12: 747-756.
[21] Censor Y, Gibali A, Reich S. Extensions of Korpelevich’s extragradient method for the variational inequality problem in Euclidean space [J]. Optimization, 2012, 61(9): 1119-1132.
[22] Popov L D. A modification of the Arrow-Hurwicz method for search of saddle points [J]. Mathematical Notes of the Academy of Sciences of the USSR, 1980, 28(5): 845-848.
[23] Solodov M V, Svaiter B F. A new projection method for variational inequality problems [J]. SIAM Journal on Control and Optimization, 1999, 37(3): 765-776.
[24] Wang Y, Xiu N, Wang C. Unified framework of extragradient-type methods for pseudomonotone variational inequalities [J]. Journal of Optimization Theory and Applications, 2001, 111(3): 641-656.
[25] Han D. A modified alternating direction method for variational inequality problems [J]. Applied Mathematics & Optimization, 2002, 45(1): 63-74.
[26] Gao X, Cai X, Wang X. Self-adaptive inertial projection and contraction algorithm for monotone variational inequality [J]. Asia-Pacific Journal of Operational Research, 2022, 39(2): 2150021.
[27] Tseng P. A modified forward-backward splitting method for maximal monotone mappings [J]. SIAM Journal on Control and Optimization, 2000, 38(2): 431-446.
[28] Malitsky Y, Tam M. A forward-backward splitting method for monotone inclusions without cocoercivity [J]. SIAM Journal on Optimization, 2020, 30(2): 1451-1472.
[29] Ryu E K, V u B C. Finding the forward-Douglas-Rachford-forward method [J]. Journal of Optimization Theory and Applications, 2020, 184(3): 858-876.
[30] Aragón-Artacho F J, Torregrosa-Belén D. A direct proof of convergence of Davis{Yin splitting algorithm allowing larger stepsizes [J]. Set-Valued and Variational Analysis, 2022, 30(3): 1011- 1029.
北大中文核心期刊