Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

An LQP-Based Symmetric Alternating Direction Method of Multipliers with Larger Step Sizes

  • Published:
Journal of the Operations Research Society of China Aims and scope Submit manuscript

A Correction to this article was published on 27 May 2019

This article has been updated

Abstract

Symmetric alternating direction method of multipliers (ADMM) is an efficient method for solving a class of separable convex optimization problems. This method updates the Lagrange multiplier twice with appropriate step sizes at each iteration. However, such step sizes were conservatively shrunk to guarantee the convergence in recent studies. In this paper, we are devoted to seeking larger step sizes whenever possible. The logarithmic-quadratic proximal (LQP) terms are applied to regularize the symmetric ADMM subproblems, allowing the constrained subproblems to then be converted to easier unconstrained ones. Theoretically, we prove the global convergence of such LQP-based symmetric ADMM by specifying a larger step size domain. Moreover, the numerical results on a traffic equilibrium problem are reported to demonstrate the advantage of the method with larger step sizes.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Change history

  • 27 May 2019

    The correct fund note for the original version is provided in this correction.

References

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

    Article  MATH  Google Scholar 

  2. He, B., Xu, Y., Yuan, X.: A logarithmic-quadratic proximal prediction–correction method for structured monotone variational inequalities. Comput. Optim. Appl. 35, 19–46 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  3. Yang, H., Huang, H.: Mathematical and Economic Theory of Road Pricing. Elsevier, Amsterdam (2005)

    Book  Google Scholar 

  4. He, B., Ma, F., Yuan, X.: Convergence study on the symmetric version of ADMM with larger step sizes. SIAM J. Imaging Sci. 9, 1467–1501 (2016)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

  6. Glowinski, R., Marroco, 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. Rev. Francaise Automat. Inform. Rech. Opér. Sér. Rouge Anal. Numér 9, 41–76 (1975)

    MATH  Google Scholar 

  7. Eckstein, J., Yao, W.: Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives. Pac. J. Optim. 11, 619–644 (2015)

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. He, B., Liu, H., Wang, Z., Yuan, X.: A strictly contractive Peaceman–Rachford splitting method for convex programming. SIAM J. Optim. 24, 1011–1040 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  10. Auslender, A., Teboulle, M., Ben-Tiba, S.: A logarithmic-quadratic proximal method for variational inequalities. In: Computational Optimization, pp. 31–40. Springer (1999)

  11. Li, M., Yuan, X.: A strictly contractive Peaceman–Rachford splitting method with logarithmic-quadratic proximal regularization for convex programming. Math. Oper. Res. 40, 842–858 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Yuan, X., Li, M.: An LQP-based decomposition method for solving a class of variational inequalities. SIAM J. Optim. 21, 1309–1318 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  13. Auslender, A., Teboulle, M.: Entropic proximal decomposition methods for convex programs and variational inequalities. Math. Program. 91, 33–47 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  14. Auslender, A., Teboulle, M.: The log-quadratic proximal methodology in convex optimization algorithms and variational inequalities. In: Equilibrium Problems and Variational Models, pp. 19–52. Springer (2003)

  15. Han, D.: A hybrid entropic proximal decomposition method with self-adaptive strategy for solving variational inequality problems. Comput. Math. Appl. 55, 101–115 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  16. Bai, J., Zhang, H., Li, J., Xu, F.: Generalized symmetric ADMM for separable convex optimization. Comput. Optim. Appl. 70(1), 129–170 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  17. Gu, Y., Jiang, B., Han, D.: A semi-proximal-based strictly contractive Peaceman–Rachford splitting method. arXiv:1506.02221 (2015)

  18. Chen, C., Li, M., Yuan, X.: Further study on the convergence rate of alternating direction method of multipliers with logarithmic-quadratic proximal regularization. J. Optim. Theory Appl. 166, 906–929 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  19. Li, M., Li, X., Yuan, X.: Convergence analysis of the generalized alternating direction method of multipliers with logarithmic-quadratic proximal regularization. J. Optim. Theory Appl. 164, 218–233 (2015)

    Article  MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  21. Tao, M., Yuan, X.: On the O(1/\(t\)) convergence rate of alternating direction method with logarithmic-quadratic proximal regularization. SIAM J. Optim. 22, 1431–1448 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  22. He, H., Wang, K., Cai, X., Han, D.: An LQP-based two-step method for structured variational inequalities. J. Oper. Res. Soc. China 5, 301–317 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  23. Nagurney, A., Zhang, D.: Projected Dynamical Systems and Variational Inequalities with Applications. International Series in Operations Research and Management Science. Springer, New York (1996)

    Google Scholar 

  24. Li, M.: A hybrid LQP-based method for structured variational inequalities. Int. J. Comput. Math. 89(10), 1412–1425 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors are grateful to thank the two anonymous referees for their helpful suggestions.

Author information

Authors and Affiliations

  1. School of Economics and Management, Southeast University, Nanjing, 210096, China

    Zhong-Ming Wu

  2. School of Management and Engineering, Nanjing University, Nanjing, 210093, China

    Min Li

Authors
  1. Zhong-Ming Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Min Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zhong-Ming Wu.

Additional information

The original version of this article was revised with correct fund note.

This research was supported by National Natural Science Foundation of China Grant 11771078, Natural Science Foundation of Jiangsu Province Grant BK20181258, Project of 333 of Jiangsu Province Grant BRA2018351 and Postgraduate Research & Practice Innovation Program of Jiangsu Province Grant KYCX18_0200.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Wu, ZM., Li, M. An LQP-Based Symmetric Alternating Direction Method of Multipliers with Larger Step Sizes. J. Oper. Res. Soc. China 7, 365–383 (2019). https://doi.org/10.1007/s40305-019-00247-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40305-019-00247-y

Keywords

Mathematics Subject Classification