A General Analysis of the Convergence of ADMM
作者： Robert Nishihara , Laurent Lessard , Ben Recht , Andrew Packard , Michael Jordan
DOI:
关键词:
摘要: We provide a new proof of the linear convergence of the alternating direction method of multipliers (ADMM) when one of the objective terms is strongly convex. Our proof is based on a framework for analyzing optimization algorithms introduced in Lessard et al.(2014), reducing algorithm convergence to verifying the stability of a dynamical system. This approach generalizes a number of existing results and obviates any assumptions about specific choices of algorithm parameters. On a numerical example, we demonstrate that …
arxiv.org参考文章(34)
James Kwok, Ruiliang Zhang, Asynchronous Distributed ADMM for Consensus Optimization international conference on machine learning. pp. 1701- 1709 ,(2014)
Alberto Bemporad, Lorenzo Stella, Panagiotis Patrinos, Forward-backward truncated Newton methods for convex composite optimization arXiv: Optimization and Control. ,(2014)
Wei Deng, Wotao Yin, On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers Journal of Scientific Computing. ,vol. 66, pp. 889- 916 ,(2016) , 10.1007/S10915-015-0048-X
Arindam Banerjee, Huahua Wang, Online Alternating Direction Method arXiv: Learning. ,(2012)
M. Corless, Guaranteed rates of exponential convergence for uncertain systems Journal of Optimization Theory and Applications. ,vol. 64, pp. 481- 494 ,(1990) , 10.1007/BF00939420
Pontus Giselsson, Stephen Boyd, Diagonal scaling in Douglas-Rachford splitting and ADMM conference on decision and control. pp. 5033- 5039 ,(2014) , 10.1109/CDC.2014.7040175
J. Eckstein, Parallel alternating direction multiplier decomposition of convex programs Journal of Optimization Theory and Applications. ,vol. 80, pp. 39- 62 ,(1994) , 10.1007/BF02196592
P. L. Lions, B. Mercier, Splitting Algorithms for the Sum of Two Nonlinear Operators SIAM Journal on Numerical Analysis. ,vol. 16, pp. 964- 979 ,(1979) , 10.1137/0716071
Bo Wahlberg, Stephen Boyd, Mariette Annergren, Yang Wang, An ADMM Algorithm for a Class of Total Variation Regularized Estimation Problems IFAC Proceedings Volumes. ,vol. 45, pp. 83- 88 ,(2012) , 10.3182/20120711-3-BE-2027.00310
Euhanna Ghadimi, Iman Shames, André Teixeira, Mikael Johansson, Optimal Parameter Selection for the Alternating Direction Method of Multipliers (ADMM): Quadratic Problems IEEE Transactions on Automatic Control. ,vol. 60, pp. 644- 658 ,(2015) , 10.1109/TAC.2014.2354892