×

An inexact ADMM with proximal-indefinite term and larger stepsize. (English) Zbl 1508.90061

Summary: In this paper, an inexact Alternating Direction Method of Multipliers (ADMM) has been proposed for solving the two-block separable convex optimization problem subject to linear equality constraints. The first resulting subproblem is solved inexactly under relative error criterion, while another subproblem called regularization problem is solved inexactly by introducing an indefinite proximal term. Meanwhile, the dual variable is updated twice with relatively larger stepsizes since an indefinite proximal term is exploited. By reformulating the first-order optimality conditions of the involved subproblems as a monotone inclusion problem, the sublinear convergence rate of the proposed algorithm is established in the pointwise and ergodic sense. Numerical experiments on testing two sparse optimization problems from statistical learning and image restoration indicate that our inexact ADMM performs much better than several well-established algorithms.

MSC:

90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adona, V.; Goncalves, M.; Melo, J., An inexact proximal generalized alternating direction method of multipliers, Comput. Optim. Appl., 76, 621-647 (2020) · Zbl 1445.90077
[2] Adona, V.; Goncalves, M., An inexact version of the symmetric proximal ADMM for solving separable convex optimization (2020), pp. 1-26
[3] Adona, V.; Goncalves, M.; Melo, J., Iteration-complexity analysis of a generalized alternating direction method of multipliers, J. Glob. Optim., 73, 331-348 (2019) · Zbl 1482.90143
[4] Beck, A., First Order Methods in Optimization (2017), SIAM: SIAM Philadelphia · Zbl 1384.65033
[5] Boyd, S.; Parikh, N.; Chu, E.; Peleato, B.; Eckstein, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3, 1-122 (2010) · Zbl 1229.90122
[6] Bai, J.; Li, J.; Xu, F.; Zhang, H., Generalized symmetric ADMM for separable convex optimization, Comput. Optim. Appl., 70, 129-170 (2018) · Zbl 1461.65126
[7] Bai, J.; Hager, W.; Zhang, H., An inexact accelerated stochastic ADMM for separable convex optimization, Comput. Optim. Appl., 81, 479-518 (2022) · Zbl 1487.90521
[8] Bai, J.; Han, D.; Sun, H.; Zhang, H., Convergence on a symmetric accelerated stochastic ADMM with larger stepsizes, CSIAM Trans. Appl. Math., 3, 448-479 (2022)
[9] Bai, J.; Ma, Y.; Sun, H.; Zhang, M., Iteration complexity analysis of a partial LQP-based alternating direction method of multipliers, Appl. Numer. Math., 165, 500-518 (2021) · Zbl 1465.65048
[10] Bai, J.; Zhang, H.; Li, J., A parameterized proximal point algorithm for separable convex optimization, Optim. Lett., 12, 1589-1608 (2018) · Zbl 1407.90250
[11] Bai, J., A new insight on augmented Lagrangian method with applications in machine learning, Optim. Online (2021)
[12] Bai, J.; Bian, F.; Chang, X.; Du, L., Accelerated stochastic Peaceman-Rachford method for empirical risk minimization, Optim. Online (2021)
[13] Burachik, R.; Sagastizabal, C.; Svaiter, B., ϵ-enlargements of maximal monotone operators: theory and applications, reformulation: nonsmooth, piecewise smooth, semismooth and smoothing methods, (Applied Optimization. Applied Optimization, Lausanne, 1997, vol. 22 (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, the Netherlands), 25-43 · Zbl 0928.65068
[14] Chang, X.; Bai, J.; Song, D.; Liu, S., Linearized symmetric multi-block ADMM with indefinite proximal regularization and optimal proximal parameter, Calcolo, 57, 1-36 (2020) · Zbl 1467.65061
[15] Chen, C.; Li, M.; Liu, X.; Ye, Y., Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights, Math. Program., 173, 37-77 (2019) · Zbl 1415.90079
[16] Chen, J.; Wang, Y.; He, H.; Lv, Y., Convergence analysis of positive-indefinite proximal ADMM with a Glowinski’s relaxation factor, Numer. Algorithms, 83, 1415-1440 (2020) · Zbl 1461.65137
[17] Deng, W.; Yin, W., On the global and linear convergence of the generalized alternating direction method of multipliers, J. Sci. Comput., 66, 889-916 (2016) · Zbl 1379.65036
[18] Eckstein, J.; Bertsekas, D., On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55, 293-318 (1992) · Zbl 0765.90073
[19] Eckstein, J.; Silva, P., A practical relative error criterion for augmented Lagrangians, Math. Program., 141, 319-348 (2013) · Zbl 1362.90312
[20] Eckstein, J.; Yao, W., Approximate ADMM algorithms derived from Lagrangian splitting, Comput. Optim. Appl., 68, 363-405 (2017) · Zbl 1378.90063
[21] Gabay, D.; Mercier, B., A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2, 17-40 (1976) · Zbl 0352.65034
[22] Gao, B.; Ma, F., Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization, J. Optim. Theory Appl., 176, 178-204 (2018) · Zbl 1453.65133
[23] 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, Rev. Fr. Autom. Inform. Rech. Opér., Anal. Numér., 9, 41-76 (1975) · Zbl 0368.65053
[24] Han, D.; Sun, D.; Zhang, L., Linear rate convergence of the alternating direction method of multipliers for convex composite programming, Math. Oper. Res., 43, 622-637 (2018) · Zbl 1440.90047
[25] Hager, W.; Yashtini, M.; Zhang, H., An \(\mathcal{O}(1 / k)\) convergence rate for the variable stepsize Bregman operator splitting algorithm, SIAM J. Numer. Anal., 54, 1535-1556 (2016) · Zbl 1381.49009
[26] Hager, W.; Zhang, H., Convergence rates for an inexact ADMM applied to separable convex optimization, Comput. Optim. Appl., 77, 729-754 (2020) · Zbl 1466.90072
[27] He, H.; Han, D.; Li, Z., Some projection methods with the BB step sizes for variational inequalities, J. Comput. Appl. Math., 236, 2590-2604 (2012) · Zbl 1317.65150
[28] He, B.; Ma, F.; Yuan, X., Convergence study on the symmetric version of ADMM with larger step sizes, SIAM J. Imaging Sci., 9, 1467-1501 (2016) · Zbl 1381.90066
[29] He, B.; Xu, H.; Yuan, X., On the proximal Jacobian decomposition of ALM for multiple-block separable convex minimization problems and its relationship to ADMM, J. Sci. Comput., 66, 1204-1217 (2016) · Zbl 1371.65052
[30] He, B.; Ma, F.; Yuan, X., Optimally linearizing the alternating direction method of multipliers for convex programming, Comput. Optim. Appl., 75, 361-388 (2020) · Zbl 1432.90111
[31] Hestenes, M., Multiplier and gradient methods, J. Optim. Theory Appl., 4, 303-320 (1969) · Zbl 0174.20705
[32] Jiang, F.; Wu, Z.; Cai, X., Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization, J. Ind. Manag. Optim., 16, 835-856 (2020) · Zbl 1449.90290
[33] Kinderlehrer, D.; Stampacchia, G., An Introduction to Variational Inequalities and Their Applications (2000), SIAM · Zbl 0988.49003
[34] Liu, Z.; Li, J.; Li, G.; Bai, J.; Liu, X., A new model for sparse and low rank matrix decomposition, J. Appl. Anal. Comput., 7, 600-616 (2017) · Zbl 1488.65103
[35] Sun, W.; Yuan, Y., Optimization Theory and Methods (2006), Springer: Springer Boston · Zbl 1129.90002
[36] Peaceman, D.; Rachford, H., The numerical solution of parabolic and elliptic differential equations, J. Soc. Ind. Appl. Math., 3, 28-41 (1955) · Zbl 0067.35801
[37] Rockafellar, R.; Wets, R., Variational Analysis (1998), Springer-Verlag: Springer-Verlag Berlin · Zbl 0888.49001
[38] Shen, Y.; Zuo, Y.; Yu, A., A partially proximal S-ADMM for separable convex optimization with linear constraints, Appl. Numer. Math., 160, 65-83 (2021) · Zbl 1459.90159
[39] Solodov, M.; Svaiter, B., A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator, Set-Valued Anal., 7, 323-345 (1999) · Zbl 0959.90038
[40] Tao, M., Convergence study of indefinite proximal ADMM with a relaxation factor, Comput. Optim. Appl., 77, 91-123 (2020) · Zbl 1447.90033
[41] Wu, Z.; Li, M., General inexact primal-dual hybrid gradient methods for saddle-point problems and convergence analysis, Asia-Pac. J. Oper. Res., 8, 1-27 (2021)
[42] Wu, Z.; Li, M., An LQP-based symmetric alternating direction method of multipliers with larger step sizes, J. Oper. Res. Soc. China, 7, 365-383 (2019) · Zbl 1438.49049
[43] Wu, Z.; Song, Y.; Jiang, F., Inexact generalized ADMM with relative error criteria for linearly constrained convex optimization problems, Optim. Lett. (2022), in press
[44] Xiao, Y.; Chen, L.; Li, D., A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming, Math. Program. Comput., 10, 533-555 (2018) · Zbl 1411.90260
[45] Xie, J.; Liao, A.; Yang, X., An inexact alternating direction method of multipliers with relative error criteria, Optim. Lett., 11, 583-596 (2017) · Zbl 1367.90089
[46] Yang, J.; Zhang, Y., Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing, SIAM J. Sci. Comput., 33, 250-278 (2011) · Zbl 1256.65060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.