Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Inexact asymmetric forward-backward-adjoint splitting algorithms for saddle point problems

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

Adopting a suitable approximation strategy can both enhance the robustness and improve the efficiency of the numerical algorithms. In this paper, we suggest combining two approximation criteria, the absolute one and the relative one, to the asymmetric forward-backward-adjoint splitting (AFBA) algorithm for a class of convex-concave saddle point problems, resulting in two inexact AFBA variants. These two approximation criteria are low-cost, since verifying them just involves the subgradient of a certain function. For both the absolute error AFBA and the relative error AFBA, we establish the global convergence and the O(1/N) convergence rate measured by the gap function in the ergodic sense, where N is the number of iterations. For the absolute error AFBA, we show that it possesses an O(1/N2) (linear convergence) rate of convergence, under the assumption that a part of (both) the underlying functions are strongly convex. We report some numerical results which demonstrate the effectiveness of the proposed methods.

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

Algorithm 1
Algorithm 2
Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Data availability

Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.

References

  1. Cai, X., Guo, K., Jiang, F., Wang, K., Wu, Z., Han, D.: The developments of proximal point algorithms. J. Oper. Res. Soc. China 10, 197–239 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  2. Cai, X., Han, D., Xu, L.: An improved first-order primal-dual algorithm with a new correction step. J. Glob. Optim. 57, 1419–1428 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  3. Chambolle, A., Ehrhardt, M. J., Richtárik, P., Schonlieb, C. -B.: Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications. SIAM J. Optim. 28, 2783–2808 (2018)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  5. Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal–dual algorithm. Math. Program. 159, 253–287 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  6. Chen, P., Huang, J., Zhang, X.: A primal–dual fixed point algorithm for convex separable minimization with applications to image restoration. Inverse Probl. 29, 025011 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chen, P., Huang, J., Zhang, X.: A primal-dual fixed point algorithm for minimization of the sum of three convex separable functions. J. Fixed Point Theory Appl. 2016, 1–18 (2016)

    MathSciNet  MATH  Google Scholar 

  8. Condat, L.: A primal–dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl. 158, 460–479 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  9. Eckstein, J., Silva, P. J.: A practical relative error criterion for augmented Lagrangians. Math. Program. 141, 319–348 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  10. Eckstein, J., Yao, W.: Approximate ADMM algorithms derived from Lagrangian splitting. Comput. Optim. Appl. 68, 363–405 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  11. Eckstein, J., Yao, W.: Relative-error approximate versions of Douglas–Rachford splitting and special cases of the ADMM. Math. Program. 170, 417–444 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  12. Esser, E., Zhang, X., Chan, T. F.: A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3, 1015–1046 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Han, D.: A survey on some recent developments of alternating direction method of multipliers. J. Oper. Res. Soc. China 10, 1–52 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  14. Han, D., He, H., Yang, H., Yuan, X.: A customized Douglas–Rachford splitting algorithm for separable convex minimization with linear constraints. Numer. Math. 127, 167–200 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  15. He, B., Yuan, X.: Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective. SIAM J. Imaging Sci. 5, 119–149 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  16. He, H., Desai, J., Wang, K.: A primal–dual prediction–correction algorithm for saddle point optimization. J. Glob. Optim. 66, 573–583 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  17. He, Y., Monteiro, R. D.: An accelerated HPE-type algorithm for a class of composite convex-concave saddle-point problems. SIAM J. Optim. 26, 29–56 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  18. Hien, L. T. K., Zhao, R., Haskell, W. B.: An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems, arXiv preprint arXiv:1711.03669 (2017)

  19. Jalilzadeh, A.: Primal-dual incremental gradient method for nonsmooth and convex optimization problems. Optim. Lett. 15, 2541–2554 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  20. Jiang, F., Cai, X., Wu, Z., Han, D.: Approximate first-order primal-dual algorithms for saddle point problems. Math. Comput. 90, 1227–1262 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  21. Jiang, F., Wu, Z., Cai, X., Zhang, H.: A first-order inexact primal-dual algorithm for a class of convex-concave saddle point problems. Numer. Algorithms 88, 1109–1136 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  22. Jiang, F., Wu, Z., Cai, X., Zhang, H.: Unified linear convergence of first-order primal-dual algorithms for saddle point problems. Optim. Lett. 16, 1675–1700 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  23. Latafat, P., Patrinos, P.: Asymmetric forward–backward–adjoint splitting for solving monotone inclusions involving three operators. Comput. Optim. Appl. 68, 57–93 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  24. Liu, Y., Xu, Y., Yin, W.: Acceleration of primal-dual methods by preconditioning and simple subproblem procedures. J. Sci. Comput. 86, 1–34 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  25. Malitsky, Y., Pock, T.: A first-order primal-dual algorithm with linesearch. SIAM J. Optim. 28, 411–432 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  26. Morini, B., Porcelli, M., Chan, R. H.: A reduced newton method for constrained linear least-squares problems. J. Comput. Appl. Math. 233, 2200–2212 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  27. Nam, S., Davies, M. E., Elad, M., Gribonval, R.: The cosparse analysis model and algorithms. Appl. Comput. Harmon. Anal. 34, 30–56 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  28. Parikh, N., Boyd, S., et al.: Proximal algorithms. Foundations and TrendsⓇ, in Optimization 1, 127–239 (2014)

    Article  Google Scholar 

  29. Rasch, J., Chambolle, A.: Inexact first-order primal-dual algorithms. Comput. Optim. Appl. 2, 381–430 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  30. Rebegoldi, S., Calatroni, L.: Scaled, inexact, and adaptive generalized fista for strongly convex optimization. SIAM J. Optim. 32, 2428–2459 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  31. Shi, F., Cheng, J., Wang, L., Yap, P. -T., Shen, D.: Low-rank total variation for image super-resolution. In: International Conference on Medical Image Computing and Computer-Assisted Intervention, Springer, pp 155–162 (2013)

  32. Shi, F., Cheng, J., Wang, L., Yap, P. -T., Shen, D.: LRTV: MR image super-resolution with low-rank and total variation regularizations. IEEE Trans. Med. Imaging 34, 2459–2466 (2015)

    Article  Google Scholar 

  33. Tan, Z., Eldar, Y. C., Beck, A., Nehorai, A.: Smoothing and decomposition for analysis sparse recovery. IEEE Trans. Signal Process. 62, 1762–1774 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  34. Vũ, B. C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. 38, 667–681 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  35. Wang, K., He, H.: A double extrapolation primal-dual algorithm for saddle point problems. J. Sci. Comput. 85, 1–30 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  36. Xie, J.: on inexact ADMMs with relative error criteria. Comput. Optim. Appl. 71, 743–765 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  37. Yan, M.: A new primal-dual algorithm for minimizing the sum of three functions with a linear operator. J. Sci. Comput. 76, 1698–1717 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  38. Zhu, M., Chan, T.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration, UCLA CAM Report, 34 (2008)

Download references

Funding

This research was partially supported by the National Natural Science Foundation of China (Nos. 11625105, 11871279, 12131004, 12126603, and 12201309) and the Startup Foundation for Introducing Talent of NUIST (No. 2022r027).

Author information

Authors and Affiliations

  1. Department of Information and Computing Science, School of Mathematics and Statistics, Nanjing University of Information Science and Technology, Nanjing, 210044, China

    Fan Jiang

  2. School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing, 210023, China

    Xingju Cai

  3. School of Mathematical Sciences, Beihang University, LMIB and NSLSCS, Beijing, 100191, China

    Deren Han

Authors
  1. Fan Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xingju Cai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Deren Han
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

All authors contributed equally to the manuscript and read and approved the final manuscript.

Corresponding author

Correspondence to Deren Han.

Ethics declarations

Ethical approval and consent to participate

Not applicable.

Consent for publication

All authors approved the final manuscript and the submission to this journal.

Human and animal ethics

Not applicable.

Competing interests

The authors declare no competing interests.

Additional information

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jiang, F., Cai, X. & Han, D. Inexact asymmetric forward-backward-adjoint splitting algorithms for saddle point problems. Numer Algor 94, 479–509 (2023). https://doi.org/10.1007/s11075-023-01509-w

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-023-01509-w

Keywords

Search

Navigation