May  2021, 17(3): 1173-1185. doi: 10.3934/jimo.2020016

The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex

High-Tech Institute of Xi'an, Xi'an 710025, China

* Corresponding author: Feng Ma

Received  January 2019 Revised  June 2019 Published  January 2020

Fund Project: The first author is supported by NSFC grants 11701564 and 11871029

The alternating direction method of multipliers (ADMM) is one of the most well-known optimization scheme for solving linearly constrained separable convex problem. In the literature, Fortin and Glowinski proved that the step size for updating the Lagrange multiplier of the ADMM can be chosen in the open interval of zero to the golden ratio. But, it is still unknown whether the dual step size can be larger than the golden ratio. In this paper, for the case where one function term is strongly convex and the associate coefficient matrix is full column rank, we present an affirmative answer to the above question. We then derive an exact relationship between the modulus and the dual step size. Our analysis deepens the understanding of the convergence properties of the ADMM.

Citation: Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial & Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016
References:
[1]

F. BachR. JenattonJ. Mairal and G. Obozinski, Optimization with sparsity-inducing penalties, Found. Trends Mach. Learn., 4 (2012), 1-106.  doi: 10.1561/2200000015.  Google Scholar

[2]

S. BoydN. ParikhE. ChuB. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2010), 1-122.  doi: 10.1561/2200000016.  Google Scholar

[3]

X. J. CaiD. Han and X. M. Yuan, 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 (2017), 39-73.  doi: 10.1007/s10589-016-9860-y.  Google Scholar

[4]

C. H. ChenB. S. HeY. Y. Ye and X. M. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5.  Google Scholar

[5]

W. Deng and W. T. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, J. Sci. Comput., 66 (2016), 889-916.  doi: 10.1007/s10915-015-0048-x.  Google Scholar

[6]

J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318.  doi: 10.1007/BF01581204.  Google Scholar

[7]

J. Eckstein and M. Fukushima, Some reformulation and applications of the alternating direction method of multipliers, Large Scale Optimization, Kluwer Acad. Publ., Dordrecht, (1994), 115–134. doi: 10.1007/978-1-4613-3632-7_7.  Google Scholar

[8]

J. Eckstein and W. Yao, Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives, Pacific J. Optim., 11 (2015), 619-644.   Google Scholar

[9]

M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solutions of Boundary Value Problems, Studies in Mathematics and its Applications, 15. North-Holland Publishing Co., Amsterdam, 1983.  Google Scholar

[10]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appli., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[11]

R. Glowinski and A. Marrocco, 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 Fr. Autom. Inform. Rech. Opér., Anal. Numér., 9 (1975), 41-76.  doi: 10.1051/m2an/197509R200411.  Google Scholar

[12]

R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer Series in Computational Physics, Springer-Verlag, New York, 1984. doi: 10.1007/978-3-662-12613-4.  Google Scholar

[13]

R. Glowinski, On alternating direction methods of multipliers: A historical perspective, Modeling, Simulation and Optimization for Science and Technology, Computational Methods in Applied Sciences, Springer, Dordrecht, 34 (2014), 59-82.  doi: 10.1007/978-94-017-9054-3_4.  Google Scholar

[14]

R. Glowinski, S. J. Osher and W. T. Yin, Splitting Methods in Communication, Imaging, Science, and Engineering, Scientific Computation. Springer, Cham, 2016. doi: 10.1007/978-3-319-41589-5.  Google Scholar

[15]

D. Han and X. M. Yuan, A note on the alternating direction method of multiplier, J. Optim. Theory Appl, 155 (2012), 227-238.  doi: 10.1007/s10957-012-0003-z.  Google Scholar

[16]

B. S. HeH. LiuZ. R. Wang and X. M. Yuan, A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM J. Optim., 24 (2014), 1011-1040.  doi: 10.1137/13090849X.  Google Scholar

[17]

B. S. HeF. Ma and X. M. Yuan, Convergence study on the symmetric version of ADMM with larger step sizes, SIAM J. Imaging Sci., 9 (2016), 1467-1501.  doi: 10.1137/15M1044448.  Google Scholar

[18]

B. S. He and X. M. Yuan, On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Num. Anal., 50 (2012), 700-709.  doi: 10.1137/110836936.  Google Scholar

[19]

B. S. He and X. M. Yuan, On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numer. Math., 130 (2015), 567-577.  doi: 10.1007/s00211-014-0673-6.  Google Scholar

[20]

M. Y. Hong and Z.-Q. Luo, On the linear convergence of the alternating direction method of multipliers, Math. Program., 162 (2017), 165-199.  doi: 10.1007/s10107-016-1034-2.  Google Scholar

[21]

Y. ShenZ. W. Wen and Y. Zhang, Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Optim. Methods Softw., 29 (2014), 239-263.  doi: 10.1080/10556788.2012.700713.  Google Scholar

[22]

M. Tao and X. M. Yuan, On Glowinski's open question on the alternating direction method of multipliers, J. Optim. Theory Appl., 179 (2018), 163-196.  doi: 10.1007/s10957-018-1338-x.  Google Scholar

[23]

Z. W. WenD. Goldfarb and W. T. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2 (2010), 203-230.  doi: 10.1007/s12532-010-0017-1.  Google Scholar

[24]

J. F. YangY. Zhang and W. T. Yin, A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data, IEEE J. Selec. Topics Signal Proc., 4 (2010), 288-297.  doi: 10.1109/JSTSP.2010.2042333.  Google Scholar

show all references

References:
[1]

F. BachR. JenattonJ. Mairal and G. Obozinski, Optimization with sparsity-inducing penalties, Found. Trends Mach. Learn., 4 (2012), 1-106.  doi: 10.1561/2200000015.  Google Scholar

[2]

S. BoydN. ParikhE. ChuB. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Found. Trends Mach. Learn., 3 (2010), 1-122.  doi: 10.1561/2200000016.  Google Scholar

[3]

X. J. CaiD. Han and X. M. Yuan, 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 (2017), 39-73.  doi: 10.1007/s10589-016-9860-y.  Google Scholar

[4]

C. H. ChenB. S. HeY. Y. Ye and X. M. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5.  Google Scholar

[5]

W. Deng and W. T. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, J. Sci. Comput., 66 (2016), 889-916.  doi: 10.1007/s10915-015-0048-x.  Google Scholar

[6]

J. Eckstein and D. P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318.  doi: 10.1007/BF01581204.  Google Scholar

[7]

J. Eckstein and M. Fukushima, Some reformulation and applications of the alternating direction method of multipliers, Large Scale Optimization, Kluwer Acad. Publ., Dordrecht, (1994), 115–134. doi: 10.1007/978-1-4613-3632-7_7.  Google Scholar

[8]

J. Eckstein and W. Yao, Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives, Pacific J. Optim., 11 (2015), 619-644.   Google Scholar

[9]

M. Fortin and R. Glowinski, Augmented Lagrangian Methods: Applications to the Numerical Solutions of Boundary Value Problems, Studies in Mathematics and its Applications, 15. North-Holland Publishing Co., Amsterdam, 1983.  Google Scholar

[10]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Comput. Math. Appli., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[11]

R. Glowinski and A. Marrocco, 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 Fr. Autom. Inform. Rech. Opér., Anal. Numér., 9 (1975), 41-76.  doi: 10.1051/m2an/197509R200411.  Google Scholar

[12]

R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer Series in Computational Physics, Springer-Verlag, New York, 1984. doi: 10.1007/978-3-662-12613-4.  Google Scholar

[13]

R. Glowinski, On alternating direction methods of multipliers: A historical perspective, Modeling, Simulation and Optimization for Science and Technology, Computational Methods in Applied Sciences, Springer, Dordrecht, 34 (2014), 59-82.  doi: 10.1007/978-94-017-9054-3_4.  Google Scholar

[14]

R. Glowinski, S. J. Osher and W. T. Yin, Splitting Methods in Communication, Imaging, Science, and Engineering, Scientific Computation. Springer, Cham, 2016. doi: 10.1007/978-3-319-41589-5.  Google Scholar

[15]

D. Han and X. M. Yuan, A note on the alternating direction method of multiplier, J. Optim. Theory Appl, 155 (2012), 227-238.  doi: 10.1007/s10957-012-0003-z.  Google Scholar

[16]

B. S. HeH. LiuZ. R. Wang and X. M. Yuan, A strictly contractive Peaceman-Rachford splitting method for convex programming, SIAM J. Optim., 24 (2014), 1011-1040.  doi: 10.1137/13090849X.  Google Scholar

[17]

B. S. HeF. Ma and X. M. Yuan, Convergence study on the symmetric version of ADMM with larger step sizes, SIAM J. Imaging Sci., 9 (2016), 1467-1501.  doi: 10.1137/15M1044448.  Google Scholar

[18]

B. S. He and X. M. Yuan, On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM J. Num. Anal., 50 (2012), 700-709.  doi: 10.1137/110836936.  Google Scholar

[19]

B. S. He and X. M. Yuan, On non-ergodic convergence rate of Douglas-Rachford alternating direction method of multipliers, Numer. Math., 130 (2015), 567-577.  doi: 10.1007/s00211-014-0673-6.  Google Scholar

[20]

M. Y. Hong and Z.-Q. Luo, On the linear convergence of the alternating direction method of multipliers, Math. Program., 162 (2017), 165-199.  doi: 10.1007/s10107-016-1034-2.  Google Scholar

[21]

Y. ShenZ. W. Wen and Y. Zhang, Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization, Optim. Methods Softw., 29 (2014), 239-263.  doi: 10.1080/10556788.2012.700713.  Google Scholar

[22]

M. Tao and X. M. Yuan, On Glowinski's open question on the alternating direction method of multipliers, J. Optim. Theory Appl., 179 (2018), 163-196.  doi: 10.1007/s10957-018-1338-x.  Google Scholar

[23]

Z. W. WenD. Goldfarb and W. T. Yin, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Program. Comput., 2 (2010), 203-230.  doi: 10.1007/s12532-010-0017-1.  Google Scholar

[24]

J. F. YangY. Zhang and W. T. Yin, A fast alternating direction method for TVL1-L2 signal reconstruction from partial Fourier data, IEEE J. Selec. Topics Signal Proc., 4 (2010), 288-297.  doi: 10.1109/JSTSP.2010.2042333.  Google Scholar

[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]

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

[3]

Ondrej Budáč, Michael Herrmann, Barbara Niethammer, Andrej Spielmann. On a model for mass aggregation with maximal size. Kinetic & Related Models, 2011, 4 (2) : 427-439. doi: 10.3934/krm.2011.4.427

[4]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[5]

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

[6]

Joel Fotso Tachago, Giuliano Gargiulo, Hubert Nnang, Elvira Zappale. Multiscale homogenization of integral convex functionals in Orlicz Sobolev setting. Evolution Equations & Control Theory, 2021, 10 (2) : 297-320. doi: 10.3934/eect.2020067

[7]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225

[13]

Sohana Jahan. Discriminant analysis of regularized multidimensional scaling. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 255-267. doi: 10.3934/naco.2020024

[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]

Vieri Benci, Sunra Mosconi, Marco Squassina. Preface: Applications of mathematical analysis to problems in theoretical physics. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : i-i. doi: 10.3934/dcdss.2020446

[16]

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

[17]

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

[18]

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

[19]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1

[20]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367

2019 Impact Factor: 1.366

Article outline

[Back to Top]