• Previous Article
    Selecting the supply chain financing mode under price-sensitive demand: confirmed warehouse financing vs. trade credit
  • JIMO Home
  • This Issue
  • Next Article
    Bayesian decision making in determining optimal leased term and preventive maintenance scheme for leased facilities
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

* Corresponding author: Xingju Cai

Received  July 2019 Revised  October 2019 Published  March 2020

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.

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 & Management Optimization, doi: 10.3934/jimo.2020053
References:
[1]

H. AttouchJ. BolteB. 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.  Google Scholar

[2]

L. E. GibbonsD. W. HearnP. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

Y. Gu, B. Jiang and D. R. Han, A semi-proximal-based strictly contractive Peaceman-Rachford splitting method, arXiv: 1506.02221, 2015. Google Scholar

[6]

B. S. HeH. LiuZ. 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.  Google Scholar

[7]

B. S. HeF. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

N. Parikh and S. Boyd, Proximal algorithms, Foundations and Trends in Optimization, 1 (2014), 127-239.  doi: 10.1561/2400000003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

B. WenX. 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.  Google Scholar

[21]

Z. B. XuX. Y. ChangF. 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.   Google Scholar

show all references

References:
[1]

H. AttouchJ. BolteB. 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.  Google Scholar

[2]

L. E. GibbonsD. W. HearnP. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

Y. Gu, B. Jiang and D. R. Han, A semi-proximal-based strictly contractive Peaceman-Rachford splitting method, arXiv: 1506.02221, 2015. Google Scholar

[6]

B. S. HeH. LiuZ. 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.  Google Scholar

[7]

B. S. HeF. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

N. Parikh and S. Boyd, Proximal algorithms, Foundations and Trends in Optimization, 1 (2014), 127-239.  doi: 10.1561/2400000003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

B. WenX. 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.  Google Scholar

[21]

Z. B. XuX. Y. ChangF. 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.   Google Scholar

Figure 1.  The relationship between $ \alpha $ and $ \theta $
[1]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185

[2]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[3]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053

[4]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29

[5]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133

[6]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[7]

Haibo Cui, Haiyan Yin. Convergence rate of solutions toward stationary solutions to the isentropic micropolar fluid model in a half line. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020210

[8]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212

[9]

Luigi C. Berselli, Jishan Fan. Logarithmic and improved regularity criteria for the 3D nematic liquid crystals models, Boussinesq system, and MHD equations in a bounded domain. Communications on Pure & Applied Analysis, 2015, 14 (2) : 637-655. doi: 10.3934/cpaa.2015.14.637

[10]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[11]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[12]

Nizami A. Gasilov. Solving a system of linear differential equations with interval coefficients. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2739-2747. doi: 10.3934/dcdsb.2020203

[13]

Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020378

[14]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271

[15]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[16]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[17]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[18]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[19]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81

[20]

Fumihiko Nakamura. Asymptotic behavior of non-expanding piecewise linear maps in the presence of random noise. Discrete & Continuous Dynamical Systems - B, 2018, 23 (6) : 2457-2473. doi: 10.3934/dcdsb.2018055

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (106)
  • HTML views (361)
  • Cited by (0)

Other articles
by authors

[Back to Top]