Help
Cart
Skip main navigation

Available Issues

April 10, 2013 - May 8, 2026

Available Issues

April 10, 2013 - May 8, 2026

Convergence Rate Analysis for the Alternating Direction Method of Multipliers with a Substitution Procedure for Separable Convex Programming

Published Online:7 Feb 2017https://doi.org/10.1287/moor.2016.0822

References

  • Blum E, Oettli W (1975) Mathematische Optimierung, Econometrics and Operations Research, 20 (Springer, Berlin).Crossref, Google Scholar
  • Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2010) Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Machine Learn. 3(1):1–122.Crossref, Google Scholar
  • Chan RH, Yang JF, Yuan XM (2011) Alternating direction method for image inpainting sin wavelet domain. SIAM J. Image Sci. 4(3):807–826.Crossref, Google Scholar
  • Chan TF, Glowinski R (1978) Finite element approximation and iterative solution of a class of mildly non-linear elliptic equations. Stanford report STAN-CS-78-674, Computer Science Department, Stanford University, Palo Alto, CA.Google Scholar
  • Chen CH, He BS, Yuan XM (2012) Matrix completion via alternating direction method. IMA J. Numer. Anal. 32(1):227–245.Crossref, Google Scholar
  • Chen CH, He BS, Ye YY, Yuan XM (2016) The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Program 155(1):57–79.Crossref, Google Scholar
  • Donoho DL (2006) Compressed sensing. IEEE Trans. Inform. Theory 52(4):1289–1306.Crossref, Google Scholar
  • Eckstein J, Bertsekas DP (1992) On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1):293–318.Crossref, Google Scholar
  • Esser E (2009) Applications of Lagrangian-based alternating direction methods and connections to split Bregman. UCLA CAM Report, Los Angeles.Google Scholar
  • Facchinei F, Pang JS (2003) Finite-Dimensional Variational Inequalities and Complementarity Problems, Springer Series in Operations Research, Vol. I (Springer, New York).Google Scholar
  • Fortin M, Glowinski R (1983) Augmented Lagrangian methods: Applications to the numerical solutions of boundary value problems. Stud. Math. Appl. Vol. 15 (North-Holland, Amsterdam).Google Scholar
  • Fukushima M (1992) Application of the alternating direction method of multipliers to separable convex programming problems. Comput. Optim. Appli. 1(1):93–111.Crossref, Google Scholar
  • Gabay D, Mercier B (1976) A dual algorithm for the solution of nonlinear variational problems via finite-element approximations. Comput. Math. Appli. 2(1):17–40.Crossref, Google Scholar
  • Glowinski R (1984) Numerical Methods for Nonlinear Variational Problems (Springer, New York).Crossref, Google Scholar
  • Glowinski R, Le Tallec P (1989) Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics. Studies in Applied Mathematics (SIAM, Philadelphia).Crossref, Google Scholar
  • Glowinski R, Marrocco A (1975) Sur l’approximation par éléments finis d’ordre un et résolution par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires. Rev. Fr. Autom. Inf. Rech. Oper. Anal. Numér R2:41–76.Google Scholar
  • Han DR, Yuan XM (2012) A note on the alternating direction method of multipliers. J. Optim. Theory Appli. 155(1):227–238.Crossref, Google Scholar
  • Hansen PC, Nagy JG, O’Leary DP (2006) Deblurring Images: Matrices, Spectra, and Filtering (SIAM, Philadelphia).Crossref, Google Scholar
  • He BS, Tao M, Yuan XM (2012) Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2):313–340.Crossref, Google Scholar
  • He BS, Tao M, Yuan XM (2015) A splitting method for separable convex programming. IMA J. Numer. Anal. 35(1):394–426.Crossref, Google Scholar
  • He BS, Xu MH, Yuan XM (2011) Solving large-scale least squares covariance matrix problems by alternating direction methods. SIAM J. Matrix Anal. Appli. 32(1):136–152.Crossref, Google Scholar
  • He BS, Liao LZ, Han DR, Yang H (2002) A new inexact alternating directions method for monontone variational inequalities. Math. Program. 92(1):103–118.Crossref, Google Scholar
  • Hestenes MR (1969) Multiplier and gradient methods. J. Optim. Theory Appli. 4(5):303–320.Crossref, Google Scholar
  • Hong MY, Luo ZQ (2016) On the linear convergence of the alternating direction method of multipliers. Math. Programm. ePub ahead of print July 6, http://doi.org/10.1007/s10107-016-1034-2.Crossref, Google Scholar
  • Huang YM, Ng MK, Wen YW (2009) Fast image restoration methods for impulse and Gaussian noise removal. IEEE Signal Process. Lett. 16(6):457–460.Crossref, Google Scholar
  • Hwang H, Haddad A (1995) Adaptive median filters: New algorithms and results. IEEE Trans. Image Process. 4(4):499–502.Crossref, Google Scholar
  • Kontogiorgis S, Meyer RR (1998) A variable-penalty alternating directions method for convex optimization. Math. Program. 83(1):29–53.Crossref, Google Scholar
  • Lan G, Monteiro RDC (2016) Iteration-complexity of first-order augmented Lagrangian methods for convex programming. Math. Program. 155(1):511–547.Crossref, Google Scholar
  • Martinet B (1970) Regularision d’inéquations variationnelles par approximations successive. Revue Francaise d’Automatique et Informatique Recherche Opérationnelle 126:154–159.Google Scholar
  • Necoara I, Suykens J (2008) Application of a smoothing technique to decomposition in convex optimization. IEEE Trans. Auto. Control 53(11):2674–2679.Crossref, Google Scholar
  • Nedelcu V, Necorara I, Tran-Ding Q (2014) Computational complexity of inexact gradient augmented Lagrangian methods: Application to constrained MPC. SIAM J. Control Optim. 52(5):3109–3134.Crossref, Google Scholar
  • Ng MK, Wang F, Yuan XM (2011) Inexact alternating direction methods for image recovery. SIAM J. Sci. Comput. 33(4):1643–1668.Crossref, Google Scholar
  • Ng MK, Weiss PA, Yuan XM (2010) Solving constrained total-variation problems via alternating direction methods. SIAM J. Sci. Comput. 32(5):2710–2736.Crossref, Google Scholar
  • Ng MK, Yuan XM, Zhang WX (2013) On variational image decomposition model for blurred images with missing pixel values. IEEE Trans. Image Processing 22(6):2233–2246.Crossref, Google Scholar
  • Peng YG, Ganesh A, Wright J, Xu WL, Ma Y (2012) Robust alignment by sparse and low-rank decomposition for linearly correlated images. IEEE Tran. Pattern Anal. Machine Intelligence 34(11):2233–2246.Crossref, Google Scholar
  • Powell MJD (1969) A method for nonlinear constraints in minimization problems. Fletcher R, ed. Optimization (Academic Press, New York), 283–298.Google Scholar
  • Rockafellar RT (1976) Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2):97–116.Link, Google Scholar
  • Rudin L, Osher S, Fatemi E (1992) Nonlinear total variation based noise removal algorithms. Physica D. 60(1-4):259–268.Crossref, Google Scholar
  • Ruszczyński A (1993) Parallel decomposition of multistage stochastic programming problems. Math. Program. 58(1):201–228.Crossref, Google Scholar
  • Sun J, Zhang S (2010) A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs. Eur. J. Oper. Res. 207(3):1210–1220.Crossref, Google Scholar
  • Tao M, Yuan XM (2011) Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21(1):57–81.Crossref, Google Scholar
  • Tibshirani R, Saunders M, Rosset S, Zhu J, Knight K (2005) Sparsity and smoothness via the fused lasso. J. Royal Statist. Soc. 67(1):91–108.Crossref, Google Scholar
  • Tran-Dinh Q, Necoara I, Diehl M (2014) Path-following gradient-based decomposition algorithms for separable convex optimization. J. Global Optim. 59(1):59–80.Crossref, Google Scholar
  • Tran-Dinh Q, Necoara I, Savorgnans C, Diehl M (2013) An inexact perturbed path-following method for Lagrangian decomposition in large-scale separable convex optimization. SIAM J. Optim. 23(1):95–125.Crossref, Google Scholar
  • Tseng P (1991) Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Con. Optim. 29(1):119–138.Crossref, Google Scholar
  • Zhang S, Ang J, Sun J (2013) An alternating direction method for solving convex nonlinear semidefinite programming problems. Optim. 62(4):527–543.Crossref, Google Scholar
  • Zhang XQ, Burger M, Osher S (2010) A unified primal-dual algorithm framework based on Bregman iteration. J. Sci. Comput. 46(1):20–46.Crossref, Google Scholar
  • Zhou Z, Li X, Wright J, Candes EJ, Ma Y (2010) Stable principal component pursuit. Proc. IEEE Intern. Sympos. Inform. Theory, ISIT ’10 (IEEE, Piscataway, NJ) 1518–1522.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree