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

Feng Ma; Jiansheng Shu; Yaxiong Li; Jian Wu

doi:10.3934/jimo.2020016

Article Contents

2021, Volume 17, Issue 3: 1173-1185. Doi: 10.3934/jimo.2020016

This issue Previous Article Mean-variance investment and contribution decisions for defined benefit pension plans in a stochastic framework Next Article Fit revelation strategy in a supply chain with two types of consumers

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
^* Corresponding author: Feng Ma

Received: December 31, 2018

Revised: May 31, 2019

Early access: January 2020

Published: May 2021

The first author is supported by NSFC grants 11701564 and 11871029

Abstract Full Text(HTML) Related Papers Cited by

Abstract

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.

Keywords:

Alternating direction method of multipliers,
convex programming,
convergence analysis,
larger step size.

Mathematics Subject Classification: Primary: 65K10, 90C25; Secondary: 49M29, 90C30.

Citation:

FullText(HTML)

Related Papers

Cited by

References

[1]	F. Bach, R. Jenatton, J. Mairal and G. Obozinski, Optimization with sparsity-inducing penalties, Found. Trends Mach. Learn., 4 (2012), 1-106. doi: 10.1561/2200000015.
[2]	S. Boyd, N. Parikh, E. Chu, B. 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.
[3]	X. J. Cai, D. 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.
[4]	C. H. Chen, B. S. He, Y. 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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[16]	B. S. He, H. Liu, Z. 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.
[17]	B. S. He, F. 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.
[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.
[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.
[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.
[21]	Y. Shen, Z. 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.
[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.
[23]	Z. W. Wen, D. 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.
[24]	J. F. Yang, Y. 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.