zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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.

90C25Convex 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 · doi:10.1016/0898-1221(76)90003-1
[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 · doi:10.1007/BF01582566
[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 · doi:10.1007/BF01581204
[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 · doi:10.1007/BF00247655
[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 · doi:10.1007/s101070100280
[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 · doi:10.1137/0329006
[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 · doi:10.1137/100807247
[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 · doi:10.1093/imanum/drq039
[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 · doi:10.1137/090768813
[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 · doi:10.1137/090774823
[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 · doi:10.1016/j.ejor.2010.07.020
[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 · doi:10.1137/100781894
[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 · doi:10.1137/090777761
[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 · doi:10.1561/2200000016
[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 · doi:10.1007/s10444-011-9172-9
[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 · doi:10.1137/S1052623495288064
[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 · doi:10.1016/j.jvcir.2009.10.006
[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