AN INEXACT SYMMETRIC PROXIMAL ADMM WITH CONVEX COMBINATION PROXIMAL CENTERS FOR SEPARABLE CONVEX PROGRAMMING

  • Jinbao JIAN ,
  • Xianke TANG ,
  • Jianghua YIN ,
  • Xianzhen JIANG
Expand
  • School of Mathematical Sciences, Center for Applied Mathematics of Guangxi, Guangxi Minzu University, Nanning 530006, China
Jinbao JIAN, E-mail: jianjb@gxu.edu.cn; Xianke TANG, E-mail: xktang2034@163.com; Xianzhen JIANG, E-mail: yl2811280@163.com

Received date: 2024-06-19

  Revised date: 2024-09-11

  Online published: 2025-10-10

Supported by

National Nat-ural Science Foundation of China (12171106), the Guangxi Science and Technology Program (AD23023001), the Natural Science Foundation of Guangxi Province (2023GXNSFBA026029), the National Natural Science Foundation of China (12401403, 12361063), the Research Project of Guangxi Minzu University (2022KJQD03), the Middle-aged and Young Teachers' Basic Ability Promotion Project of Guangxi Province (2023KY0168) and the Xiangsihu Young Scholars Innovative Research Team of Guangxi Minzu University (2022GXUNXSHQN04).

Abstract

In this paper, we develop an inexact symmetric proximal alternating direction method of multipliers (ISPADMM) with two convex combinations (ISPADMM-tcc) for solving two-block separable convex optimization problems with linear equality constraints. Specifically, the convex combination technique is incorporated into the proximal centers of both subproblems. We then approximately solve these two subproblems based on relative error criteria. The global convergence, and $O(\frac{1}{N})$ ergodic sublinear convergence rate measured by the function value residual and constraint violation are established under some mild conditions, where $N$ denotes the number of iterations. Finally, numerical experiments on solving the $l_1$-regularized analysis sparse recovery and the elastic net regularization regression problems illustrate the feasibility and effectiveness of the proposed method.

Cite this article

Jinbao JIAN , Xianke TANG , Jianghua YIN , Xianzhen JIANG . AN INEXACT SYMMETRIC PROXIMAL ADMM WITH CONVEX COMBINATION PROXIMAL CENTERS FOR SEPARABLE CONVEX PROGRAMMING[J]. Acta mathematica scientia, Series B, 2025 , 45(4) : 1701 -1722 . DOI: 10.1007/s10473-025-0424-z

References

[1] Adona V A, Gonçalves M L. An inexact version of the symmetric proximal ADMM for solving separable convex optimization. Numer Algorithms, 2023, 94(1): 1-28
[2] Adona V A, Gonçalves M L, Melo J G. Iteration-complexity analysis of a generalized alternating direction method of multipliers. J Global Optim, 2019, 73(2): 331-348
[3] Anantachai P, Poom K, Juan M. Augmented Lagrangian method for TV-$l_{1}$-$l_{2}$ based colour image restoration. J Comput Appl Math, 2019, 354: 507-519
[4] Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imaging Sci, 2009, 2(1): 183-202
[5] Bertsekas D P.Constrained Optimization and Lagrange Multiplier Methods. New York: Academic Press, 1982
[6] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn, 2011, 3(1): 1-122
[7] Candes E J, Recht B. Exact matrix completion via convex optimization. Commun ACM, 2012, 55(6): 111-119
[8] Chang X K, Yang J F. A golden ratio primal-dual algorithm for structured convex optimization. J Sci Comput, 2021, 87(2): 1-26
[9] Chang X K, Yang J F, Zhang H C. Golden ratio primal-dual algorithm with linesearch. SIAM J Optim, 2022, 32(3): 1584-1613
[10] Chen H M, Gu G Y, Yang J F. A golden ratio proximal alternating direction method of multipliers for separable convex optimization. J Global Optim, 2023, 87(2): 581-602
[11] Chen L, Sun D F, Toh K. An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming. Math Program, 2017, 161: 237-270
[12] Combettes P L, Wajs V R. Signal recovery by proximal forward-backward splitting. Multiscale Model Simul, 2005, 4: 1168-1200
[13] Douglas J, Rachford H H. On the numerical solution of the heat conduction problem in two and three space variables. Trans Amer Math Soc, 1956, 82: 420-439
[14] Eckstein J, Bertsekas D P. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math Program, 1992, 55: 293-318
[15] Eckstein J, Yao W. Approximate ADMM algorithms derived from Lagrangian splitting. Comput Optim Appl, 2017, 68: 363-405
[16] Eckstein J, Yao W. Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM. Math Program, 2018, 170(2): 417-444
[17] Eckstein J, Yao W. Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives. Pac J Optim, 2015, 11(4): 619-644
[18] Fazel M, Pong T K, Sun D F, Tseng P. Hankel matrix rank minimization with applications to system identification and realization. SIAM J Matrix Anal Appl, 2013, 34(3): 946-977
[19] Gabay D. Applications of the method of multipliers to variational inequalities// Fortin M, Glowinski R. Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems. Amsterdam: Elsevier, 1983, 15: 299-331
[20] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput Math Appl, 1976, 2: 17-40
[21] Gao X, Xu Y Y, Zhang S Z. Randomized primal-dual proximal block coordinate updates. J Oper Res Soc China, 2019, 7(2): 205-250
[22] Glowinski R, Marroco A. Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problémes de dirichlet non linéaires. ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 1975, 9: 41-76
[23] Gonçalves M L, Melo J G, Monteiro R D. On the iteration-complexity of a non-Euclidean hybrid proximal extragradient framework and of a proximal ADMM. Optim, 2020, 69(4): 847-873
[24] Gu Y, Jiang B, Han D R. A semi-proximal-based strictly contractive Peaceman-Rachford splitting method. J Comput Math, 2023, 41(6): 1017-1040
[25] Han D R. A survey on some recent developments of alternating direction method of multipliers. J Oper Res Soc China, 2022, 10(1): 1-52
[26] He B S, Liao L Z, Han D R, Yang H. A new inexact alternating directions method for monotone variational inequalities. Math Program, 2002, 92: 103-118
[27] He B S, Liu H, Wang Z R, Yuan X M. A strictly contractive Peaceman-Rachford splitting method for convex programming. SIAM J Optim, 2014, 24: 1011-1040
[28] He B S, Ma F, Yuan X M. Convergence study on the symmetric version of ADMM with larger step sizes. SIAM J Imaging Sci, 2016, 9: 1467-1501
[29] He B S, Ma F, Yuan X M. Optimally linearizing the alternating direction method of multipliers for convex programming. Comput Optim Appl, 2020, 75(2): 361-388
[30] Hestenes M R. Multiplier and gradient methods. J Optim Theory Appl, 1969, 4: 303-320
[31] Jiang F, Wu Z M. An inexact symmetric ADMM algorithm with indefinite proximal term for sparse signal recovery and image restoration problems. J Comput Appl Math, 2023, 417: 114628
[32] Li M, Yuan X M. A strictly contractive Peaceman-Rachford splitting method with logarithmic-quadratic proximal regularization for convex programming. Math Oper Res, 2015, 40(4): 842-858
[33] Li X, Yuan X M. A proximal strictly contractive Peaceman-Rachford splitting method for convex programming with applications to imaging. SIAM J Imaging Sci, 2015, 8(2): 1332-1365
[34] Lions P L, Mercier B. Splitting algorithms for the sum of two nonlinear operators. SIAM J Numer Anal, 1979, 16: 964-979
[35] Ma Y X, Bai J C, Sun H. An inexact ADMM with proximal-indefinite term and larger stepsize. Appl Numer Math, 2023, 184: 542-566
[36] Malitsky Y. Golden ratio algorithms for variational inequalities. Math Program, 2020, 184: 383-410
[37] Monteiro R D, Sim C. Complexity of the relaxed Peaceman-Rachford splitting method for the sum of two maximal strongly monotone operators. Comput Optim Appl, 2018, 70: 763-790
[38] Nocedal J, Wright S J. Numerical Optimization. New York: Springer, 2006
[39] Peaceman D W, Rachford H H. The numerical solution of parabolic and elliptic differential equations. J Soc Ind Appl Math, 1955, 3(1): 28-41
[40] Rockafellar R T. Convex Analysis.Princeton: Princeton Universerty Press, 1970
[41] Rockafellar R T, Wets R. Variational Analysis. Berlin: Springer, 2009
[42] Solodov M V, Svaiter B F. A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Anal, 1999, 7(4): 323-345
[43] Solodov M V, Svaiter B F. An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions. Math Oper Res, 2000, 25(2): 214-230
[44] Sun M, Liu J. A proximal Peaceman-Rachford splitting method for compressive sensing. J Appl Math Comput, 2016, 50: 349-363
[45] Tao M, Yuan X M. Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J Optim, 2011, 21(1), 57-81
[46] Tibshirani R. Regression shrinkage and selection via the lasso. J R Stat Soc Ser B, 1996, 58: 267-288
[47] Wu Z M, Song Y, Jiang F. Inexact generalized ADMM with relative error criteria for linearly constrained convex optimization problems. Optim Lett, 2024, 18(2): 447-470
[48] Xie J X. On inexact ADMMs with relative error criteria. Comput Optim Appl, 2018, 71(3): 743-765
[49] Xie J X, Liao A P, Yang X B. An inexact alternating direction method of multipliers with relative error criteria. Optim Lett, 2017, 11: 583-596
[50] Xu Y Y. Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. SIAM J Optim, 2017, 27(3): 1459-1484
[51] Yang J F, Zhang Y. Alternating direction algorithms for $l_{1}$-problems in compressive sensing. SIAM J Sci Comput, 2011, 33(1): 250-278
[52] Yuan X M. Alternating direction method for covariance selection models. J Sci Comput, 2012, 51: 261-273
[53] Zhou D Q, Xu H W, Yang J F. Proximal alternating direction method of multipliers with convex combination proximal centers. Asia-Pac J Oper Res, 2024, 41(3): 1-28
[54] Zuo H, Hastie T. Regularization and variable selection via the elastic net. J R Stat Soc Ser B Stat Methodol, 2005, 67(2): 301-320
Options
Outlines

/