Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: Calcolo 4/2020

01.12.2020

Linearized symmetric multi-block ADMM with indefinite proximal regularization and optimal proximal parameter

verfasst von: Xiaokai Chang, Jianchao Bai, Dunjiang Song, Sanyang Liu

Erschienen in: Calcolo | Ausgabe 4/2020

Einloggen, um Zugang zu erhalten
share
TEILEN

Abstract

The proximal term plays a significant role in the literature of proximal Alternating Direction Method of Multipliers (ADMM), since (positive-definite or indefinite) proximal terms can promote convergence of ADMM and further simplify the involved subproblems. However, an overlarge proximal parameter decelerates the convergence numerically, though the convergence can be established with it. In this paper, we thus focus on a Linearized Symmetric ADMM (LSADMM) with proper proximal terms for solving a family of multi-block separable convex minimization models, and we determine an optimal (smallest) value of the proximal parameter while convergence of this LSADMM can be still ensured. Our LSADMM partitions the data into two group variables and updates the Lagrange multiplier twice in different forms with suitable step sizes. The region of the proximal parameter, involved in the second group subproblems, is partitioned into the union of three different sets. We show the global convergence and sublinear ergodic convergence rate of LSADMM for the two cases, while a counter-example is given to illustrate that convergence of LSADMM can not be guaranteed for the remaining case. Theoretically, we obtain the optimal lower bound of the proximal parameter. Numerical experiments on the so-called latent variable Gaussian graphical model selection problems are presented to demonstrate performance of the proposed algorithm and the significant advantage of the optimal lower bound of the proximal parameter.
Literatur
1.
Zurück zum Zitat Bai, J., Li, J., Fengmin, X., Zhang, H.: Generalized symmetric ADMM for separable convex optimization. Comput. Optim. Appl. 70(1), 129–170 (2018) MathSciNetMATHCrossRef Bai, J., Li, J., Fengmin, X., Zhang, H.: Generalized symmetric ADMM for separable convex optimization. Comput. Optim. Appl. 70(1), 129–170 (2018) MathSciNetMATHCrossRef
3.
Zurück zum Zitat Partridge, M., Jabri, M.: Robust principal component analysis? J. ACM 58(3), 1–37 (2011) MathSciNet Partridge, M., Jabri, M.: Robust principal component analysis? J. ACM 58(3), 1–37 (2011) MathSciNet
4.
Zurück zum Zitat Tao, M., Yuan, X.: Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21(1), 57–81 (2011) MathSciNetMATHCrossRef Tao, M., Yuan, X.: Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21(1), 57–81 (2011) MathSciNetMATHCrossRef
5.
Zurück zum Zitat He, B., Yuan, X.: A class of ADMM-based algorithms for three-block separable convex programming. Comput. Optim. Appl. 70(3), 791–826 (2018) MathSciNetMATHCrossRef He, B., Yuan, X.: A class of ADMM-based algorithms for three-block separable convex programming. Comput. Optim. Appl. 70(3), 791–826 (2018) MathSciNetMATHCrossRef
6.
Zurück zum Zitat Han, D., Kong, W., Zhang, W.: A partial splitting augmented lagrangian method for low patch-rank image decomposition. J. Math. Imaging Vis. 51(1), 145–160 (2015) MathSciNetMATHCrossRef Han, D., Kong, W., Zhang, W.: A partial splitting augmented lagrangian method for low patch-rank image decomposition. J. Math. Imaging Vis. 51(1), 145–160 (2015) MathSciNetMATHCrossRef
7.
Zurück zum Zitat Sun, D., Toh, K.-C., Yang, L.: A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with \(4\)-type of constraints. SIAM J. Optim. 25(2), 882–915 (2014) MATH Sun, D., Toh, K.-C., Yang, L.: A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with \(4\)-type of constraints. SIAM J. Optim. 25(2), 882–915 (2014) MATH
8.
Zurück zum Zitat Li, X., Sun, D., Toh, K.C.: A schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions. Math. Program. 155(1–2), 333–373 (2016) MathSciNetMATHCrossRef Li, X., Sun, D., Toh, K.C.: A schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions. Math. Program. 155(1–2), 333–373 (2016) MathSciNetMATHCrossRef
9.
Zurück zum Zitat Chen, L., Sun, D., Toh, K.C.: An efficient inexact symmetric gauss-seidel based majorized ADMM for high-dimensional convex composite conic programming. Math. Program. 161(1–2), 237–270 (2017) MathSciNetMATHCrossRef Chen, L., Sun, D., Toh, K.C.: An efficient inexact symmetric gauss-seidel based majorized ADMM for high-dimensional convex composite conic programming. Math. Program. 161(1–2), 237–270 (2017) MathSciNetMATHCrossRef
10.
Zurück zum Zitat Chang, X., Liu, S., Li, X.: Modified alternating direction method of multipliers for convex quadratic semidefinite programming. Nerocomputing 214, 575–586 (2016) CrossRef Chang, X., Liu, S., Li, X.: Modified alternating direction method of multipliers for convex quadratic semidefinite programming. Nerocomputing 214, 575–586 (2016) CrossRef
11.
Zurück zum Zitat Glowinski, R., Marrocco, 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. J. Equine Vet. Sci. 2(R–2), 41–76 (1975) MATH Glowinski, R., Marrocco, 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. J. Equine Vet. Sci. 2(R–2), 41–76 (1975) MATH
12.
Zurück zum Zitat 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), 1–122 (2010) MATHCrossRef 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), 1–122 (2010) MATHCrossRef
13.
Zurück zum Zitat Chen, C., He, B., Ye, Y., Yuan, X.: The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program. 155(1–2), 57–79 (2016) MathSciNetMATHCrossRef Chen, C., He, B., Ye, Y., Yuan, X.: The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program. 155(1–2), 57–79 (2016) MathSciNetMATHCrossRef
14.
Zurück zum Zitat Cai, X., Han, D., Yuan, X.: On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function. Comput. Optim. Appl. 66(1), 39–73 (2017) MathSciNetMATHCrossRef Cai, X., Han, D., Yuan, X.: On the convergence of the direct extension of ADMM for three-block separable convex minimization models with one strongly convex function. Comput. Optim. Appl. 66(1), 39–73 (2017) MathSciNetMATHCrossRef
15.
Zurück zum Zitat Tao, M., Yuan, X.: Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization. Adv. Comput. Math. 44(3), 773–831 (2018) MathSciNetMATHCrossRef Tao, M., Yuan, X.: Convergence analysis of the direct extension of ADMM for multiple-block separable convex minimization. Adv. Comput. Math. 44(3), 773–831 (2018) MathSciNetMATHCrossRef
16.
Zurück zum Zitat He, B., Tao, M., Yuan, X.: Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2), 313–340 (2012) MathSciNetMATHCrossRef He, B., Tao, M., Yuan, X.: Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2), 313–340 (2012) MathSciNetMATHCrossRef
17.
Zurück zum Zitat 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) MathSciNetMATHCrossRef 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) MathSciNetMATHCrossRef
18.
19.
Zurück zum Zitat Chang, X., Liu, S., Zhao, P., Li, X.: Convergent prediction–correction-based ADMM for multi-block separable convex programming. J. Comput. Appl. Math. 335, 270–288 (2018) MathSciNetMATHCrossRef Chang, X., Liu, S., Zhao, P., Li, X.: Convergent prediction–correction-based ADMM for multi-block separable convex programming. J. Comput. Appl. Math. 335, 270–288 (2018) MathSciNetMATHCrossRef
20.
21.
Zurück zum Zitat Gao, B., Ma, F.: Symmetric alternating direction method with positive-indefinite proximal regularization for linearly constrained convex optimization. J. Optim. Theory Appl. 176(1), 178–204 (2018) MathSciNetMATHCrossRef Gao, B., Ma, F.: Symmetric alternating direction method with positive-indefinite proximal regularization for linearly constrained convex optimization. J. Optim. Theory Appl. 176(1), 178–204 (2018) MathSciNetMATHCrossRef
22.
Zurück zum Zitat Wang, J.J., Song, W.: An algorithm twisted from generalized ADMM for multi-block separable convex minimization models. J. Comput. Appl. Math. 309, 342–358 (2016) MathSciNetMATHCrossRef Wang, J.J., Song, W.: An algorithm twisted from generalized ADMM for multi-block separable convex minimization models. J. Comput. Appl. Math. 309, 342–358 (2016) MathSciNetMATHCrossRef
23.
Zurück zum Zitat Eckstein, J., Bertsekas, D.P.: On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1–3), 293–318 (1992) MathSciNetMATHCrossRef Eckstein, J., Bertsekas, D.P.: On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1–3), 293–318 (1992) MathSciNetMATHCrossRef
24.
Zurück zum Zitat Eckstein, J.: Parallel alternating direction multiplier decomposition of convex programs. J. Optim. Theory Appl. 80(1), 39–62 (1994) MathSciNetMATHCrossRef Eckstein, J.: Parallel alternating direction multiplier decomposition of convex programs. J. Optim. Theory Appl. 80(1), 39–62 (1994) MathSciNetMATHCrossRef
25.
Zurück zum Zitat Yang, J., Yuan, X.: Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization. Math. Comput. 82, 301–329 (2013) MathSciNetMATHCrossRef Yang, J., Yuan, X.: Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization. Math. Comput. 82, 301–329 (2013) MathSciNetMATHCrossRef
26.
Zurück zum Zitat Li, X., Mo, L., Yuan, X., Zhang, J.: Linearized alternating direction method of multipliers for sparse group and fused lasso models. Comput. Stat. Data Anal. 79(79), 203–221 (2014) MathSciNetMATHCrossRef Li, X., Mo, L., Yuan, X., Zhang, J.: Linearized alternating direction method of multipliers for sparse group and fused lasso models. Comput. Stat. Data Anal. 79(79), 203–221 (2014) MathSciNetMATHCrossRef
27.
Zurück zum Zitat Lin, Z., Liu, R., Li, H.: Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning. Mach. Learn. 99(2), 287–325 (2015) MathSciNetMATHCrossRef Lin, Z., Liu, R., Li, H.: Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning. Mach. Learn. 99(2), 287–325 (2015) MathSciNetMATHCrossRef
28.
Zurück zum Zitat He, B., Ma, F., Yuan, X.: Optimally linearizing the alternating direction method of multipliers for convex programming. Comput. Optim. Appl. 75, 361–388 (2020) MathSciNetMATHCrossRef He, B., Ma, F., Yuan, X.: Optimally linearizing the alternating direction method of multipliers for convex programming. Comput. Optim. Appl. 75, 361–388 (2020) MathSciNetMATHCrossRef
29.
Zurück zum Zitat Li, M., Sun, D., Toh, K.C.: A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization. SIAM J. Optim. 26(2), 922–950 (2016) MathSciNetMATHCrossRef Li, M., Sun, D., Toh, K.C.: A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization. SIAM J. Optim. 26(2), 922–950 (2016) MathSciNetMATHCrossRef
30.
Zurück zum Zitat Chang, X., Liu, S., Zhao, P., Song, D.: A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming. J. Comput. Appl. Math. 357, 251–272 (2019) MathSciNetMATHCrossRef Chang, X., Liu, S., Zhao, P., Song, D.: A generalization of linearized alternating direction method of multipliers for solving two-block separable convex programming. J. Comput. Appl. Math. 357, 251–272 (2019) MathSciNetMATHCrossRef
31.
Zurück zum Zitat Jiang, F., Zhongming, W., Cai, X.: Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. J. Ind. Manag. Optim. 16(2), 835–856 (2020) MathSciNetMATH Jiang, F., Zhongming, W., Cai, X.: Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. J. Ind. Manag. Optim. 16(2), 835–856 (2020) MathSciNetMATH
32.
Zurück zum Zitat Wang, Yu., Yin, W., Zeng, J.: Global convergence of ADMM in nonconvex nonsmooth optimization. J. Sci. Comput. 78(1–2), 1–35 (2018) MathSciNet Wang, Yu., Yin, W., Zeng, J.: Global convergence of ADMM in nonconvex nonsmooth optimization. J. Sci. Comput. 78(1–2), 1–35 (2018) MathSciNet
33.
Zurück zum Zitat Rockafellar, R.T.: Convex Analysis, vol. 17. Princeton University Press, Princeton (1970) MATHCrossRef Rockafellar, R.T.: Convex Analysis, vol. 17. Princeton University Press, Princeton (1970) MATHCrossRef
34.
Zurück zum Zitat Ma, S., Xue, L., Zou, H.: Alternating direction methods for latent variable Gaussian graphical model selection. Neural Comput. 25(8), 2172–2198 (2013) MathSciNetMATHCrossRef Ma, S., Xue, L., Zou, H.: Alternating direction methods for latent variable Gaussian graphical model selection. Neural Comput. 25(8), 2172–2198 (2013) MathSciNetMATHCrossRef
Metadaten
Titel
Linearized symmetric multi-block ADMM with indefinite proximal regularization and optimal proximal parameter
verfasst von
Xiaokai Chang
Jianchao Bai
Dunjiang Song
Sanyang Liu
Publikationsdatum
01.12.2020
Verlag
Springer International Publishing
Erschienen in
Calcolo / Ausgabe 4/2020
Print ISSN: 0008-0624
Elektronische ISSN: 1126-5434
DOI
https://doi.org/10.1007/s10092-020-00387-1

Weitere Artikel der Ausgabe 4/2020

Calcolo 4/2020 Zur Ausgabe

Premium Partner