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

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247

[2]

Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial & Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078

[3]

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 & Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037

[4]

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems & Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917

[5]

Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2019029

[6]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067

[7]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317

[8]

Nora Merabet. Global convergence of a memory gradient method with closed-form step size formula. Conference Publications, 2007, 2007 (Special) : 721-730. doi: 10.3934/proc.2007.2007.721

[9]

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 & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[10]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65

[11]

Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial & Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057

[12]

Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349

[13]

Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357

[14]

Yazheng Dang, Fanwen Meng, Jie Sun. Convergence analysis of a parallel projection algorithm for solving convex feasibility problems. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 505-519. doi: 10.3934/naco.2016023

[15]

Yong Duan, Jian-Guo Liu. Convergence analysis of the vortex blob method for the $b$-equation. Discrete & Continuous Dynamical Systems - A, 2014, 34 (5) : 1995-2011. doi: 10.3934/dcds.2014.34.1995

[16]

Yulan Lu, Minghui Song, Mingzhu Liu. Convergence rate and stability of the split-step theta method for stochastic differential equations with piecewise continuous arguments. Discrete & Continuous Dynamical Systems - B, 2019, 24 (2) : 695-717. doi: 10.3934/dcdsb.2018203

[17]

Su-Hong Jiang, Min Li. A modified strictly contractive peaceman-rachford splitting method for multi-block separable convex programming. Journal of Industrial & Management Optimization, 2018, 14 (1) : 397-412. doi: 10.3934/jimo.2017052

[18]

Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems & Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305

[19]

Binjie Li, Xiaoping Xie, Shiquan Zhang. New convergence analysis for assumed stress hybrid quadrilateral finite element method. Discrete & Continuous Dynamical Systems - B, 2017, 22 (7) : 2831-2856. doi: 10.3934/dcdsb.2017153

[20]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319

2018 Impact Factor: 1.025

Article outline

[Back to Top]