A note on the alternating direction method of multipliers. (English) Zbl 1255.90093

Summary: 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\geq 3\). This note shows the global convergence of this extension when the involved functions are further assumed to be strongly convex.


90C25 Convex programming
Full Text: DOI


[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) · Zbl 0352.65034
[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) · Zbl 0823.90097
[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) · Zbl 0765.90073
[5] Fukushima, M.: Application of the alternating directions method of multipliers to separable convex programming problems. Comput. Optim. Appl. 2, 93–111 (1992) · Zbl 0763.90071
[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) · Zbl 1009.90108
[7] Kontogiorgis, S., Meyer, R.R.: A variable-penalty alternating directions method for convex optimization. Math. Program. 83, 29–53 (1998) · Zbl 0920.90118
[8] Tseng, P.: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control Optim. 29, 119–138 (1991) · Zbl 0737.90048
[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) · Zbl 1234.68448
[10] Chen, C.H., He, B.S., Yuan, X.M.: Matrix completion via alternating direction method. IMA J. Numer. Anal. 32, 227–245 (2012) · Zbl 1236.65043
[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) · Zbl 1243.49039
[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) · Zbl 1217.65071
[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) · Zbl 1229.90119
[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) · Zbl 1218.90115
[16] Yang, J.F., Zhang, Y.: Alternating direction algorithms for 1 problems in compressive sensing. SIAM J. Sci. Comput. 33, 250–278 (2011) · Zbl 1256.65060
[17] Yuan, X.M., Yang, J.F.: Sparse and low-rank matrix decomposition via alternating direction method. Pac. J. Optim. (to appear) · Zbl 1269.90061
[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) · Zbl 1229.90122
[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) · Zbl 1252.78015
[20] Kiwiel, K.C., Rosa, C.H., Ruszczyński, A.: Proximal decomposition via alternating linearization. SIAM J. Optim. 9, 668–689 (1999) · Zbl 0958.65068
[21] Setzer, S., Steidl, G., Tebuber, T.: Deblurring Poissonian images by split Bregman techniques. J. Vis. Commun. Image Represent. 21, 193–199 (2010) · Zbl 05742901
[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)
[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) · Zbl 1273.90152
[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) · Zbl 1273.90122
[25] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401
[26] Facchinei, F., Pang, J.S.: Finite-Dimensional Variational Inequalities and Complementarity Problems, vols. I and II. Springer, New York (2003) · Zbl 1062.90002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.