-
Previous Article
A better dominance relation and heuristics for Two-Machine No-Wait Flowshops with Maximum Lateness Performance Measure
- JIMO Home
- This Issue
-
Next Article
Back-ordered inventory model with inflation in a cloudy-fuzzy environment
July
2021, 17(4): 1943-1971.
doi: 10.3934/jimo.2020053
The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems
| 1. | Department of Information and Computing Science, School of Mathematics and Statistics, Nanjing University of Information Science and Technology, Nanjing 210044, China |
| 2. | School of Mathematical Sciences, Key Laboratory for NSLSCS of Jiangsu Province, Nanjing Normal University, Nanjing 210023, China |
| 3. | LMIB of the Ministry of Education, School of Mathematical Sciences, Beihang University, Beijing 100191, China |
The symmetric alternating direction method of multipliers is an efficient algorithm, which updates the Lagrange multiplier twice at each iteration and the variables are treated in a symmetric manner. Considering that the convergence range of the parameters plays an important role in the implementation of the algorithm. In this paper, we analyze the convergence rate of the symmetric ADMM with a more relaxed parameter range for solving the two block nonconvex separable optimization problem under the assumption that the generated sequence is bounded. Two cases are considered. In the first case, both components of the objective function are nonconvex, we prove the convergence of the augmented Lagrangian function sequence, and establish the $ O(1/\sqrt{k}) $ worst-case complexity measured by the difference of two consecutive iterations. In the second case, one component of the objective function is convex and the error bound condition is assumed, then we can prove that the iterative sequence converges locally to a KKT point in a R-linear rate; and an auxiliary sequence converges in a Q-linear rate. Furthermore, a practical inexact symmetric ADMM with relative error criteria is proposed, and the associated convergence analysis is established under the same conditions.
Keywords:
Symmetric alternating direction method of multipliers,
nonconvex minimization,
inexact,
relative error criteria,
sublinear convergence,
linear convergence.
Mathematics Subject Classification:
90C26, 49M27, 90C33.
Citation:
Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial and Management Optimization,
2021, 17
(4)
: 1943-1971.
doi: 10.3934/jimo.2020053
![]()
References:
| [1] |
H. Attouch, J. Bolte, B. F. Svaiter and A. Soubeyran,
Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Mathematical Programming, 137 (2013), 91-129.
doi: 10.1007/s10107-011-0484-9. |
| [2] |
L. E. Gibbons, D. W. Hearn, P. M. Pardalos and M. V. Ramana,
Continuous characterizations of the maximum clique problem, Mathematics of Operations Research, 22 (1997), 754-768.
doi: 10.1287/moor.22.3.754. |
| [3] |
R. Glowinski and A. Marroco, 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, Revue Française D'Automatique, Informatique, Recherche Opérationnelle. Analyse Numérique, 9 (1975), 41–76.
doi: 10.1051/m2an/197509R200411. |
| [4] |
R. Glowinski, T. W. Pan and X. C. Tai, Some facts about operator-splitting and alternating direcrion methods, Splitting Methods in Communication, Imaging, Science, and Engineering, (2016), 19–94. |
| [5] |
Y. Gu, B. Jiang and D. R. Han, A semi-proximal-based strictly contractive Peaceman-Rachford splitting method, arXiv: 1506.02221, 2015. |
| [6] |
B. S. He, H. Liu, Z. R. Wang and X. M. Yuan,
A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM Journal on Optimization, 24 (2014), 1011-1040.
doi: 10.1137/13090849X. |
| [7] |
B. S. He, F. Ma and X. M. Yuan,
Convergence study on the symmetric version of admm with larger step sizes, SIAM Journal on Imaging Sciences, 9 (2016), 1467-1501.
doi: 10.1137/15M1044448. |
| [8] |
D. R. Han,
A new hybrid generalized proximal point algorithm for variational inequality problems, Journal of Global Optimization, 26 (2003), 125-140.
doi: 10.1023/A:1023087304476. |
| [9] |
D. R. Han,
Inexact operator splitting methods with selfadaptive strategy for variational inequality problems, Journal of Optimization Theory and Applications, 132 (2007), 227-243.
doi: 10.1007/s10957-006-9060-5. |
| [10] |
Z. H. Jia, X. Gao, X. J. Cai and D. R. Han, Local Linear Convergence of the Alternating Direction Method of Multipliers for Nonconvex Separable Optimization Problems, Manuscript, 2018. |
| [11] |
W. Kaplan,
A test for copositive matrices, Linear Algebra and its Applications, 313 (2000), 203-206.
doi: 10.1016/S0024-3795(00)00138-5. |
| [12] |
J. Liu, J. H. Chen and J. P. Ye, Large-scale sparse logistic regression, Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Paris, (2009), 547–556.
doi: 10.1145/1557019.1557082. |
| [13] |
P. L. Lions and B. Mercier,
Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numercial Analusis, 16 (1979), 964-979.
doi: 10.1137/0716071. |
| [14] |
Z. Q. Luo and P. Tseng,
Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem, SIAM Journal on Optimization, 2 (1992), 43-54.
doi: 10.1137/0802004. |
| [15] |
Z. Q. Luo and P. Tseng,
Error bounds and convergence analysis of feasible descent methods: A general approach, Annals of Operations Research, 46 (1993), 157-178.
doi: 10.1007/BF02096261. |
| [16] |
D. H. Peaceman and H. H. Rachford,
The numerical solution of parabolic and elliptic differential equations, Journal of the Society for Industrial and Applied Mathematics, 3 (1955), 28-41.
doi: 10.1137/0103003. |
| [17] |
N. Parikh and S. Boyd,
Proximal algorithms, Foundations and Trends in Optimization, 1 (2014), 127-239.
doi: 10.1561/2400000003. |
| [18] |
H. V$\ddot{a}$liaho,
Quadratic programming criteria for copositive matrices, Linear Algebra and its Applications, 119 (1989), 163-182.
doi: 10.1016/0024-3795(89)90076-1. |
| [19] |
Z. M. Wu, M. Li, David Z. W. Wang and D. R. Han, A symmetric alternating direction method of multipliers for separable nonconvex mimimization problems, Asia-Pacific Journal of Operational Research, 34 (2017), 1750030, 27pp.
doi: 10.1142/S0217595917500300. |
| [20] |
B. Wen, X. J. Chen and T. K. Pong,
Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems, SIAM Journal on Optimization, 27 (2017), 124-145.
doi: 10.1137/16M1055323. |
| [21] |
Z. B. Xu, X. Y. Chang, F. M. Xu and H. Zhang,
$ L_ {1/2}$ regularization: A thresholding representation theory and a fast solver, IEEE Transactions on Neural Networks and Learning Systems, 23 (2012), 1013-1027.
|
show all references
References:
| [1] |
H. Attouch, J. Bolte, B. F. Svaiter and A. Soubeyran,
Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Mathematical Programming, 137 (2013), 91-129.
doi: 10.1007/s10107-011-0484-9. |
| [2] |
L. E. Gibbons, D. W. Hearn, P. M. Pardalos and M. V. Ramana,
Continuous characterizations of the maximum clique problem, Mathematics of Operations Research, 22 (1997), 754-768.
doi: 10.1287/moor.22.3.754. |
| [3] |
R. Glowinski and A. Marroco, 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, Revue Française D'Automatique, Informatique, Recherche Opérationnelle. Analyse Numérique, 9 (1975), 41–76.
doi: 10.1051/m2an/197509R200411. |
| [4] |
R. Glowinski, T. W. Pan and X. C. Tai, Some facts about operator-splitting and alternating direcrion methods, Splitting Methods in Communication, Imaging, Science, and Engineering, (2016), 19–94. |
| [5] |
Y. Gu, B. Jiang and D. R. Han, A semi-proximal-based strictly contractive Peaceman-Rachford splitting method, arXiv: 1506.02221, 2015. |
| [6] |
B. S. He, H. Liu, Z. R. Wang and X. M. Yuan,
A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM Journal on Optimization, 24 (2014), 1011-1040.
doi: 10.1137/13090849X. |
| [7] |
B. S. He, F. Ma and X. M. Yuan,
Convergence study on the symmetric version of admm with larger step sizes, SIAM Journal on Imaging Sciences, 9 (2016), 1467-1501.
doi: 10.1137/15M1044448. |
| [8] |
D. R. Han,
A new hybrid generalized proximal point algorithm for variational inequality problems, Journal of Global Optimization, 26 (2003), 125-140.
doi: 10.1023/A:1023087304476. |
| [9] |
D. R. Han,
Inexact operator splitting methods with selfadaptive strategy for variational inequality problems, Journal of Optimization Theory and Applications, 132 (2007), 227-243.
doi: 10.1007/s10957-006-9060-5. |
| [10] |
Z. H. Jia, X. Gao, X. J. Cai and D. R. Han, Local Linear Convergence of the Alternating Direction Method of Multipliers for Nonconvex Separable Optimization Problems, Manuscript, 2018. |
| [11] |
W. Kaplan,
A test for copositive matrices, Linear Algebra and its Applications, 313 (2000), 203-206.
doi: 10.1016/S0024-3795(00)00138-5. |
| [12] |
J. Liu, J. H. Chen and J. P. Ye, Large-scale sparse logistic regression, Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Paris, (2009), 547–556.
doi: 10.1145/1557019.1557082. |
| [13] |
P. L. Lions and B. Mercier,
Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numercial Analusis, 16 (1979), 964-979.
doi: 10.1137/0716071. |
| [14] |
Z. Q. Luo and P. Tseng,
Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem, SIAM Journal on Optimization, 2 (1992), 43-54.
doi: 10.1137/0802004. |
| [15] |
Z. Q. Luo and P. Tseng,
Error bounds and convergence analysis of feasible descent methods: A general approach, Annals of Operations Research, 46 (1993), 157-178.
doi: 10.1007/BF02096261. |
| [16] |
D. H. Peaceman and H. H. Rachford,
The numerical solution of parabolic and elliptic differential equations, Journal of the Society for Industrial and Applied Mathematics, 3 (1955), 28-41.
doi: 10.1137/0103003. |
| [17] |
N. Parikh and S. Boyd,
Proximal algorithms, Foundations and Trends in Optimization, 1 (2014), 127-239.
doi: 10.1561/2400000003. |
| [18] |
H. V$\ddot{a}$liaho,
Quadratic programming criteria for copositive matrices, Linear Algebra and its Applications, 119 (1989), 163-182.
doi: 10.1016/0024-3795(89)90076-1. |
| [19] |
Z. M. Wu, M. Li, David Z. W. Wang and D. R. Han, A symmetric alternating direction method of multipliers for separable nonconvex mimimization problems, Asia-Pacific Journal of Operational Research, 34 (2017), 1750030, 27pp.
doi: 10.1142/S0217595917500300. |
| [20] |
B. Wen, X. J. Chen and T. K. Pong,
Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems, SIAM Journal on Optimization, 27 (2017), 124-145.
doi: 10.1137/16M1055323. |
| [21] |
Z. B. Xu, X. Y. Chang, F. M. Xu and H. Zhang,
$ L_ {1/2}$ regularization: A thresholding representation theory and a fast solver, IEEE Transactions on Neural Networks and Learning Systems, 23 (2012), 1013-1027.
|
| [1] |
Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030 |
| [2] |
Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems and Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917 |
| [3] |
Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial and Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135 |
| [4] |
Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1783-1799. doi: 10.3934/jimo.2019029 |
| [5] |
Haiyan Wang, Jinyan Fan. Convergence properties of inexact Levenberg-Marquardt method under Hölderian local error bound. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2265-2275. doi: 10.3934/jimo.2020068 |
| [6] |
Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507 |
| [7] |
Jinyan Fan, Jianyu Pan. On the convergence rate of the inexact Levenberg-Marquardt method. Journal of Industrial and Management Optimization, 2011, 7 (1) : 199-210. doi: 10.3934/jimo.2011.7.199 |
| [8] |
Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247 |
| [9] |
Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial and Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037 |
| [10] |
Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047 |
| [11] |
Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial and Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078 |
| [12] |
Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013 |
| [13] |
Weijun Zhou, Youhua Zhou. On the strong convergence of a modified Hestenes-Stiefel method for nonconvex optimization. Journal of Industrial and Management Optimization, 2013, 9 (4) : 893-899. doi: 10.3934/jimo.2013.9.893 |
| [14] |
Gonglin Yuan, Zhan Wang, Pengyuan Li. Global convergence of a modified Broyden family method for nonconvex functions. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021164 |
| [15] |
Matteo Bonforte, Jean Dolbeault, Matteo Muratori, Bruno Nazaret. Weighted fast diffusion equations (Part Ⅱ): Sharp asymptotic rates of convergence in relative error by entropy methods. Kinetic and Related Models, 2017, 10 (1) : 61-91. doi: 10.3934/krm.2017003 |
| [16] |
Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103 |
| [17] |
Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859 |
| [18] |
Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic and Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1 |
| [19] |
Jahnabi Chakravarty, Ashiho Athikho, Manideepa Saha. Convergence of interval AOR method for linear interval equations. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 293-308. doi: 10.3934/naco.2021006 |
| [20] |
Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial and Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]