article

A Note on the Alternating Direction Method of Multipliers

Authors:

Xiaoming YuanAuthors Info & Claims

Journal of Optimization Theory and Applications, Volume 155, Issue 1

Pages 227 - 238

https://doi.org/10.1007/s10957-012-0003-z

Published: 01 October 2012 Publication History

Abstract

We consider the linearly constrained separable convex programming, whose objective function is separable into m individual convex functions without coupled variables. The alternating direction method of multipliers has been well studied in the literature for the special case m=2, while it remains open whether its convergence can be extended to the general case mź3. This note shows the global convergence of this extension when the involved functions are further assumed to be strongly convex.

References

[1]

Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 2, 17---40 (1976)

[2]

Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Fortin, M., Glowinski, R. (eds.) Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, pp. 299---331. North-Holland, Amsterdam (1983)

[3]

Chen, G., Teboulle, M.: A proximal-based decomposition method for convex minimization problems. Math. Program. 64, 81---101 (1994)

[4]

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

Digital Library

[5]

Fukushima, M.: Application of the alternating directions method of multipliers to separable convex programming problems. Comput. Optim. Appl. 2, 93---111 (1992)

[6]

He, B.S., Liao, L.Z., Han, D.R., Yang, H.: A new inexact alternating direction method for monotone variational inequalities. Math. Program. 92, 103---118 (2002)

[7]

Kontogiorgis, S., Meyer, R.R.: A variable-penalty alternating directions method for convex optimization. Math. Program. 83, 29---53 (1998)

Digital Library

[8]

Tseng, P.: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control Optim. 29, 119---138 (1991)

Digital Library

[9]

Chan, R.H., Yang, J.F., Yuan, X.M.: Alternating direction method for image inpainting in wavelet domain. SIAM J. Imaging Sci. 4, 807---826 (2011)

Digital Library

[10]

Chen, C.H., He, B.S., Yuan, X.M.: Matrix completion via alternating direction method. IMA J. Numer. Anal. 32, 227---245 (2012)

[11]

Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split Bregman. UCLA CAM Report 09-31 (2009)

[12]

He, B.S., Xu, M.H., Yuan, X.M.: Solving large-scale least squares covariance matrix problems by alternating direction methods. SIAM J. Matrix Anal. Appl. 32, 136---152 (2011)

Digital Library

[13]

Ng, M.K., Weiss, P.A., Yuan, X.M.: Solving constrained total-variation problems via alternating direction methods. SIAM J. Sci. Comput. 32, 2710---2736 (2010)

Digital Library

[14]

Sun, J., Zhang, S.: A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs. Eur. J. Oper. Res. 207, 1210---1220 (2010)

[15]

Tao, M., Yuan, X.M.: Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21, 57---81 (2011)

Digital Library

[16]

Yang, J.F., Zhang, Y.: Alternating direction algorithms for ℓ1 problems in compressive sensing. SIAM J. Sci. Comput. 33, 250---278 (2011)

Digital Library

[17]

Yuan, X.M., Yang, J.F.: Sparse and low-rank matrix decomposition via alternating direction method. Pac. J. Optim. (to appear)

[18]

Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Faund. Trends Mach. Learn. 3, 1---122 (2010)

Digital Library

[19]

Bardsley, J.M., Knepper, S., Nagy, J.: Structured linear algebra problems in adaptive optics imaging. Adv. Comput. Math. 5(2---4), 103---117 (2011)

Digital Library

[20]

Kiwiel, K.C., Rosa, C.H., Ruszczyński, A.: Proximal decomposition via alternating linearization. SIAM J. Optim. 9, 668---689 (1999)

Digital Library

[21]

Setzer, S., Steidl, G., Tebuber, T.: Deblurring Poissonian images by split Bregman techniques. J. Vis. Commun. Image Represent. 21, 193---199 (2010)

Digital Library

[22]

Peng, Y.G., Ganesh, A., Wright, J., Xu, W.L., Ma, Y.: Robust alignment by sparse and low-rank decomposition for linearly correlated images. IEEE Trans. Pattern Anal. Mach. Intell. (to appear)

Digital Library

[23]

He, B.S., Tao, M., Yuan, X.M.: Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. (to appear)

[24]

He, B.S., Tao, M., Xu, M.H., Yuan, X.M.: Alternating directions based contraction method for generally separable linearly constrained convex programming problems. Optimization (to appear)

[25]

Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

[26]

Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vols. I and II. Springer, New York (2003)

Cited By

Wei LXi MGurrin CKongkachandra RSchoeffmann KDang-Nguyen DRossetto LSatoh SZhou L(2024)Subspace Clustering with A Hybrid Adaptive Graph FilterProceedings of the 2024 International Conference on Multimedia Retrieval10.1145/3652583.3658042(1070-1078)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3652583.3658042
Wei LSong SGurrin CKongkachandra RSchoeffmann KDang-Nguyen DRossetto LSatoh SZhou L(2024)Multi-view Subspace Clustering via An Adaptive Consensus Graph FilterProceedings of the 2024 International Conference on Multimedia Retrieval10.1145/3652583.3658009(776-784)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3652583.3658009
Huan MLiang JMa YLiu WWu YZeng Y(2024)Optimization of High-Resolution and Ambiguity-Free Sparse Planar Array Geometry for Automotive MIMO RadarIEEE Transactions on Signal Processing10.1109/TSP.2024.340488872(4332-4348)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3404888
Show More Cited By

A Note on the Alternating Direction Method of Multipliers

Recommendations

A note on the convergence of alternating proximal gradient method

We consider a class of linearly constrained separable convex programming problems whose objective functions are the sum of m convex functions without coupled variables. The alternating proximal gradient method is an effective method for the case m=2, ...
Inexact alternating direction methods of multipliers for separable convex optimization

Inexact alternating direction multiplier methods (ADMMs) are developed for solving general separable convex optimization problems with a linear constraint and with an objective that is the sum of smooth and nonsmooth terms. The approach involves ...
Inexact Alternating Direction Methods of Multipliers with Logarithmic---Quadratic Proximal Regularization

In the literature, it was shown recently that the Douglas---Rachford alternating direction method of multipliers can be combined with the logarithmic-quadratic proximal regularization for solving a class of variational inequalities with separable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Optimization Theory and Applications

Journal of Optimization Theory and Applications Volume 155, Issue 1

October 2012

354 pages

ISSN:0022-3239

Issue’s Table of Contents

Copyright © Copyright © 2012 Springer Science+Business Media, LLC.

Publisher

Plenum Press

United States

Publication History

Published: 01 October 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

53
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wei LXi MGurrin CKongkachandra RSchoeffmann KDang-Nguyen DRossetto LSatoh SZhou L(2024)Subspace Clustering with A Hybrid Adaptive Graph FilterProceedings of the 2024 International Conference on Multimedia Retrieval10.1145/3652583.3658042(1070-1078)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3652583.3658042
Wei LSong SGurrin CKongkachandra RSchoeffmann KDang-Nguyen DRossetto LSatoh SZhou L(2024)Multi-view Subspace Clustering via An Adaptive Consensus Graph FilterProceedings of the 2024 International Conference on Multimedia Retrieval10.1145/3652583.3658009(776-784)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3652583.3658009
Huan MLiang JMa YLiu WWu YZeng Y(2024)Optimization of High-Resolution and Ambiguity-Free Sparse Planar Array Geometry for Automotive MIMO RadarIEEE Transactions on Signal Processing10.1109/TSP.2024.340488872(4332-4348)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1109/TSP.2024.3404888
Wei LLiu SZhou RZhu CLiu J(2024)Learning Idempotent Representation for Subspace ClusteringIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.330334336:3(1183-1197)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1109/TKDE.2023.3303343
Liu XDabiri AWang YXun JDe Schutter B(2024)Distributed Model Predictive Control for Virtually Coupled Heterogeneous Trains: Comparison and AssessmentIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.345816925:12(20753-20766)Online publication date: 23-Sep-2024
https://dl.acm.org/doi/10.1109/TITS.2024.3458169
Gupta HSingh HKumar AVishwakarma ASingh G(2024)Variational mode decomposition based image denoising using semi-adaptive conductance function inspired diffusion filteringMultimedia Tools and Applications10.1007/s11042-023-15863-383:3(7433-7456)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s11042-023-15863-3
Liu WZheng XChen CHu MLiao XWang FTan YMeng DWang JEl Saddik AMei TCucchiara RBertini MTobon Vallejo DAtrey PHossain M(2023)Differentially Private Sparse Mapping for Privacy-Preserving Cross Domain RecommendationProceedings of the 31st ACM International Conference on Multimedia10.1145/3581783.3611924(6243-6252)Online publication date: 26-Oct-2023
https://dl.acm.org/doi/10.1145/3581783.3611924
Shi BShao HLin JZhao SWang S(2023)Jamming the Relay-Assisted Multi-User Wireless Communication System: A Zero-Sum Game ApproachIEEE Transactions on Information Forensics and Security10.1109/TIFS.2023.327722218(3198-3211)Online publication date: 17-May-2023
https://dl.acm.org/doi/10.1109/TIFS.2023.3277222
Cipolla SGondzio J(2023)A linear algebra perspective on the random multi-block ADMM: the QP caseCalcolo: a quarterly on numerical analysis and theory of computation10.1007/s10092-023-00546-060:4Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1007/s10092-023-00546-0
Maiseli B(2022)Edge-Preserving Multiframe Image Super-Resolution Methods Under Anisotropic Diffusion FrameworkSN Computer Science10.1007/s42979-022-01177-y3:4Online publication date: 6-May-2022
https://dl.acm.org/doi/10.1007/s42979-022-01177-y
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents