Skip to main content
SpringerLink
Log in

O(1/t) complexity analysis of the generalized alternating direction method of multipliers

  • Articles
  • Published:
Science China Mathematics Aims and scope Submit manuscript

Abstract

Owing to its efficiency in solving some types of large-scale separable optimization problems with linear constraints, the convergence rate of the alternating direction method of multipliers (ADMM for short) has recently attracted significant attention. In this paper, we consider the generalized ADMM (G-ADMM), which incorporates an acceleration factor and is more efficient. Instead of using a solution measure that depends on a bounded set and cannot be easily estimated, we propose using the original ϵ-optimal solution measure, under which we prove that the G-ADMM converges at a rate of O(1/t). The new bound depends on the penalty parameter and the distance between the initial point and solution set, which is more reasonable than the previous bound.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Boley D. Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs. SIAM J Optim, 2013, 23: 2183–2207

    Article  MathSciNet  MATH  Google Scholar 

  2. Chambolle A, Pock T. A first-order primal-dual algorithm for convex problems with applications to imaging. J Math Imaging Vision, 2011, 40: 120–145

    Article  MathSciNet  MATH  Google Scholar 

  3. Chen C, He B, Yuan X. Matrix completion via an alternating direction method. IMA J Numer Anal, 2012, 32: 227–245

    Article  MathSciNet  MATH  Google Scholar 

  4. Davis D, Yin W T. Convergence rate analysis of several splitting schemes. In: Splitting Methods in Communication, Imaging, Science, and Engineering. New York: Springer, 2016, 115–163

    Chapter  Google Scholar 

  5. Deng W, Yin W. On the global and linear convergence of the generalized alternating direction method of multipliers. J Sci Comput, 2016, 66: 889–916

    Article  MathSciNet  MATH  Google Scholar 

  6. Douglas J, Rachford H H. On the numerical solution of heat conduction problems in two and three space variables. Trans Amer Math Soc, 1956, 82: 421–421

    Article  MathSciNet  MATH  Google Scholar 

  7. Eckstein J, Bertsekas D P. An alternating direction method for linear programming. Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, https://doi.org/dspace.mit.edu/bitstream/handle/1721.1/3197/P-1967-21455306.pdf?sequence=1, 1990

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput Math Appl, 1976, 2: 17–40

    Article  MATH  Google Scholar 

  10. Glowinski R, Marrocco A. Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de Dirichlet non linéaires. RAIRO Oper Res, 1975, 2: 41–76

    MATH  Google Scholar 

  11. Goldstein T, Osher S. The split Bregman method for L 1-regularized problems. SIAM J Imaging Sci, 2009, 2: 323–343

    Article  MathSciNet  MATH  Google Scholar 

  12. Goldstein T, O’Donoghue B, Setzer S, et al. Fast alternating direction optimization methods. SIAM J Imaging Sci, 2014, 7: 1588–1623

    Article  MathSciNet  MATH  Google Scholar 

  13. Han D R, Sun D F, Zhang L W. Linear rate convergence of the alternating direction method of multipliers for convex composite programming. Math Oper Res, 2017, in press

    Google Scholar 

  14. Han D, Yuan X. Local linear convergence of the alternating direction method of multipliers for quadratic programs. SIAM J Numer Anal, 2013, 51: 3446–3457

    Article  MathSciNet  MATH  Google Scholar 

  15. He B, Liao L Z, Han D, et al. A new inexact alternating directions method for monotone variational inequalities. Math Program, 2002, 92: 103–118

    Article  MathSciNet  MATH  Google Scholar 

  16. He B, Yuan X. On the O(1/n) convergence rate of the Douglas-Rachford alternating direction method. SIAM J Numer Anal, 2012, 50: 700–709

    Article  MathSciNet  MATH  Google Scholar 

  17. Hong M, Luo Z Q. On the linear convergence of the alternating direction method of multipliers. Math Program, 2017, 162: 165–199

    Article  MathSciNet  MATH  Google Scholar 

  18. Lan G. An optimal method for stochastic composite optimization. Math Program, 2012, 133: 365–397

    Article  MathSciNet  MATH  Google Scholar 

  19. Lin T Y, Ma S Q, Zhang S Z. On the sublinear convergence rate of multi-block ADMM. J Oper Res Soc China, 2015, 3: 251–274

    Article  MathSciNet  MATH  Google Scholar 

  20. Monteiro R D C, Svaiter B F. Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J Optim, 2013, 23: 475–507

    Article  MathSciNet  MATH  Google Scholar 

  21. Nesterov Y E. A method for solving the convex programming problem with convergence rate O(1/k 2). Dokl Akad Nauk, 1983, 269: 543–547

    MathSciNet  Google Scholar 

  22. Nesterov Y E. Gradient methods for minimizing composite objective function. Core report, https://doi.org/www.ecore.be/DPs/dp-1191313936.pdf, 2007

    Google Scholar 

  23. Ng M K, Weiss P, Yuan X. Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods. SIAM J Sci Comput, 2010, 32: 2710–2736

    Article  MathSciNet  MATH  Google Scholar 

  24. Ouyang Y Y, Chen Y M, Lan G H, et al. An accelerated linearized alternating direction method of multipliers. SIAM J Imaging Sci, 2014, 8: 644–681

    Article  MathSciNet  MATH  Google Scholar 

  25. Peaceman D W, Rachford H H. The numerical solution of parabolic elliptic differential equations. J Soc Indust Appl Math, 1955, 3: 28–41

    Article  MathSciNet  MATH  Google Scholar 

  26. Setzer S, Steidl G, Teuber T. Deblurring Poissonian images by split Bregman techniques. J Vis Commun Image Represent, 2010, 21: 193–199

    Article  Google Scholar 

  27. Sun J, Zhang S. A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs. European J Oper Res, 2010, 207: 1210–1220

    Article  MathSciNet  MATH  Google Scholar 

  28. Wen Z, Goldfarb D, Yin W. Alternating direction augmented Lagrangian methods for semidefinite programming. Math Program Comput, 2010, 2: 203–230

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  30. Yang W H, Han D. Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems. SIAM J Numer Anal, 2016, 54: 625–640

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work was supported by a Project Funded Priority Academic Program Develop- ment of Jiangsu Higher Education Institutions of Jiangsu Higher Education Institutions, National Natural Sci- ence Foundation of China (Grant Nos. 11401315, 11625105, 11171159 and 11431102) and the National Science Foundation from Jiangsu Province (Grant No. BK20140914). The authors thank the referees for their constructive comments and suggestions, which helped us improve the paper greatly.

Author information

Authors and Affiliations

  1. School of Mathematical Sciences and Key Laboratory for Numerical Simulation of Large Scale Complex Systems of Jiangsu Province, Nanjing Normal University, Nanjing, 210023, China

    Xingju Cai & Deren Han

Authors
  1. Xingju Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Deren Han
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Deren Han.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cai, X., Han, D. O(1/t) complexity analysis of the generalized alternating direction method of multipliers. Sci. China Math. 62, 795–808 (2019). https://doi.org/10.1007/s11425-016-9184-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11425-016-9184-4

Keywords

MSC(2010)

Search

Navigation