[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Convergence of Bregman Peaceman–Rachford Splitting Method for Nonconvex Nonseparable Optimization

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

Abstract

This work is about a splitting method for solving a nonconvex nonseparable optimization problem with linear constraints, where the objective function consists of two separable functions and a coupled term. First, based on the ideas from Bregman distance and Peaceman–Rachford splitting method, the Bregman Peaceman–Rachford splitting method with different relaxation factors for the multiplier is proposed. Second, the global and strong convergence of the proposed algorithm are proved under general conditions including the region of the two relaxation factors as well as the crucial Kurdyka–Łojasiewicz property. Third, when the associated Kurdyka–Łojasiewicz property function has a special structure, the sublinear and linear convergence rates of the proposed algorithm are guaranteed. Furthermore, some preliminary numerical results are shown to indicate the effectiveness of the proposed algorithm.

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
£29.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 includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

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

Similar content being viewed by others

References

  1. Shen, Y., Wen, Z., Zhang, Y.: Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization. Optim. Methods Softw. 29(2), 239–263 (2014)

    MathSciNet  MATH  Google Scholar 

  2. Xu, Y.: Alternating proximal gradient method for sparse nonnegative Tucker decomposition. Math. Program. Comput. 7(1), 39–70 (2015)

    MathSciNet  MATH  Google Scholar 

  3. Yang, L.F., Luo, J.Y., Xu, Y., Zhang, Z.R., Dong, Z.Y.: A distributed dual consensus ADMM based on partition for DC-DOPF with carbon emission trading. IEEE Trans. Ind. Inform. 16(3), 1858–1872 (2020)

    Google Scholar 

  4. Douglas, J., Rachford, H.H.: On the numerical solution of heat conduction problems in two or three space variables. Trans. Am. Math. Soc. 82, 421–439 (1956)

    MathSciNet  MATH  Google Scholar 

  5. Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    MATH  Google Scholar 

  8. Glowinski, R., Marrocco, A.: Sur l’approximation, par elements finis d’ordre un, et la resolution, par penalisation-dualit’e, d’une classe de problems de Dirichlet non lineares. Ann. Math. Stat. 9, 41–76 (1975)

    Google Scholar 

  9. Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4(4), 1168–1200 (2005)

    MathSciNet  MATH  Google Scholar 

  10. Corman, E., Yuan, X.: A generalized proximal point algorithm and its convergence rate. SIAM J. Optim. 24(4), 1614–1638 (2014)

    MathSciNet  MATH  Google Scholar 

  11. Gabay, D.: Chapter IX applications of the method of multipliers to variational inequalities. Stud. Math. Appl. 15, 299–331 (1983)

    Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  13. 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)

    MathSciNet  MATH  Google Scholar 

  14. Wu, Z., Li, M.: An LQP-based symmetric alternating direction method of multipliers with larger step sizes. J. Oper. Res. Soc. China 7, 365–383 (2019)

    MathSciNet  MATH  Google Scholar 

  15. Sun, M., Wang, Y., Liu, J.: Generalized Peaceman–Rachford splitting method for multiple-block separable convex programming with applications to robust PCA. Calcolo 54(1), 77–94 (2017)

    MathSciNet  MATH  Google Scholar 

  16. Deng, Z., Liu, S.: Generalized Peaceman–Rachford splitting method with substitution for convex programming. Optim. Lett. 14, 1781–1802 (2020)

    MathSciNet  MATH  Google Scholar 

  17. Deng, Z., Liu, S.: Inertial proximal strictly contractive Peaceman–Rachford splitting method with an indefinite term for convex optimization. J. Comput. Appl. Math. 374, 112772 (2020)

    MathSciNet  MATH  Google Scholar 

  18. Li, X., Yuan, X.: A proximal strictly contractive Peaceman–Rachford splitting method for convex programming with applications to imaging. SIAM J. Imaging Sci. 8(2), 1332–1365 (2015)

    MathSciNet  MATH  Google Scholar 

  19. Dou, M.Y., Li, H.Y., Liu, X.W.: An inertial proximal Peaceman–Rachford splitting method (in Chinese). Sci. Sin. Math. 47(2), 333–348 (2017)

    MATH  Google Scholar 

  20. Lu, S., Hong, M., Wang, Z.: A nonconvex splitting method for symmetric nonnegative matrix factorization: convergence analysis and optimality. In: 2017 IEEE International Conference on Acoustics, Speech and Signal Processing 2572–2576 (2017)

  21. Olshausen, B.A., Field, D.J.: Emergence of simple-cell receptive field properties by learning a sparse code for natural images. Nature 381(6583), 607–609 (1996)

    Google Scholar 

  22. Chartrand, R., Staneva, V.: Restricted isometry properties and nonconvex compressive sensing. Inverse Probl. 24(3), 035020 (2008)

    MathSciNet  MATH  Google Scholar 

  23. Li, G., Pong, T.K.: Douglas–Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems. Math. Program. 159(1–2), 371–401 (2016)

    MathSciNet  MATH  Google Scholar 

  24. Chao, M.T., Han, D.R., Cai, X.J.: Convergence of the Peaceman–Rachford splitting method for a class of nonconvex programs. Numer. Math. Theory Methods Appl. 14(2), 438–460 (2021)

    MathSciNet  MATH  Google Scholar 

  25. Wu, Z., Li, M., Wang, D., Han, D.: A symmetric alternating direction method of multipliers for separable nonconvex minimization problems. Asia Pac. J. Oper. Res. 34(06), 1750030 (2017)

    MathSciNet  MATH  Google Scholar 

  26. Bai, J., Liang, J., Guo, K., Jing, Y.: Accelerated symmetric ADMM and its applications in signal processing (2019). arXiv:1906.12015

  27. Hong, M., Luo, Z., Razaviyayn, M.: Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26, 337–364 (2016)

    MathSciNet  MATH  Google Scholar 

  28. Gao, X., Xu, Y., Zhang, S.: Randomized primal-dual proximal block coordinate updates. J. Oper. Res. Soc. China 7, 205–250 (2019)

    MathSciNet  MATH  Google Scholar 

  29. Hong, M., Chang, T., Wang, X., Razaviyayn, M., Ma, S., Luo, Z.: A block successive upper bound minimization method of multipliers for linearly constrained convex optimization. Math. Oper. Res. 45(3), 797–1192 (2020)

    MathSciNet  MATH  Google Scholar 

  30. Chao, M.T., Cheng, C.Z., Liang, D.Y.: A proximal block minimization method of multipliers with a substitution procedure. Optim. Methods Soft. 30(4), 825–842 (2015)

    MathSciNet  MATH  Google Scholar 

  31. Gao, X., Zhang, S.: First-order algorithms for convex optimization with nonseparable objective and coupled constraints. J. Oper. Res. Soc. China 5, 131–159 (2017)

    MathSciNet  MATH  Google Scholar 

  32. Cui, Y., Li, X., Sun, D., Toh, K.: On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions. J. Optim. Theory Appl. 169, 1013–1041 (2016)

    MathSciNet  MATH  Google Scholar 

  33. Chen, C., Li, M., Liu, X., Ye, Y.: Extended ADMM and BCD for nonseparable convex minimization models with quadratic coupling terms: convergence analysis and insights. Math. Program. 173, 37–77 (2019)

    MathSciNet  MATH  Google Scholar 

  34. Liu, F., Xu, L., Sun, Y., Han, D.: A proximal alternating direction method for multi-block coupled convex optimization. J. Ind. Manag. Optim. 15, 723–737 (2018)

    MathSciNet  MATH  Google Scholar 

  35. Guo, K., Han, D., Wu, T.: Convergence analysis for optimization problems with nonseparable nonconvex objective and linear constraints. Pac. J. Optim. 14, 489–506 (2018)

    MathSciNet  MATH  Google Scholar 

  36. Guo, K., Wang, X.: Convergence of generalized alternating direction method of multipliers for nonseparable nonconvex objective with linear constraints. J. Math. Res. Appl. 38, 523–540 (2018)

    MathSciNet  MATH  Google Scholar 

  37. Chao, M., Deng, Z., Jian, J.: Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure. Complexity 2020, 1–14 (2020)

    MATH  Google Scholar 

  38. Jiang, B., Lin, T., Ma, S., Zhang, S.: Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis. Comput. Optim. Appl. 72, 115–157 (2019)

    MathSciNet  MATH  Google Scholar 

  39. Liu, Q., Shen, X., Gu, Y.: Linearized ADMM for nonconvex nonsmooth optimization with convergence analysis. IEEE Access 7, 76131–76144 (2019)

    Google Scholar 

  40. Wang, H., Banerjee, A.: Bregman alternating direction method of multipliers. In: Proceedings of Advances in Neural Information Processing Systems (NIPS), 2816–2824 (2014)

  41. Li, G., Pong, T.: Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25, 2434–2460 (2015)

    MathSciNet  MATH  Google Scholar 

  42. Wang, F., Xu, Z., Xu, H.: Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems (2014). arXiv:1410.8625

  43. Wang, F., Cao, W., Xu, Z.: Convergence of multi-block Bregman ADMM for nonconvex composite problems. Sci. China Inform. Sci. 61, 122101 (2018)

    MathSciNet  Google Scholar 

  44. Xu, J., Chao, M.: An inertial Bregman generalized alternating direction method of multipliers for nonconvex optimization. J. Appl. Math. Comput. (2021). https://doi.org/10.1007/s12190-021-01590-1

  45. Rockafellar, R., Wets, R.: Variational Analysis. Springer Science & Business Media, Berlin (2009)

    MATH  Google Scholar 

  46. Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35, 438–457 (2010)

    MathSciNet  MATH  Google Scholar 

  47. Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization or nonconvex and nonsmooth problems. Math. Program. 146, 459–494 (2014)

    MathSciNet  MATH  Google Scholar 

  48. Nesterov, Y.: Introduction Lectures on Convex Optimization: A Basic Course. Springer Science & Business Media, Berlin (2013)

    Google Scholar 

  49. Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7, 200–217 (1967)

    MathSciNet  MATH  Google Scholar 

  50. Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116, 5–16 (2009)

    MathSciNet  MATH  Google Scholar 

  51. Zeng, L., Xie, J.: Group variable selection via SCAD\(-l_{2}\). Statistics 48, 49–66 (2014)

    MathSciNet  MATH  Google Scholar 

  52. Wu, Z., Li, M.: General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems. Comput. Optim. Appl. 73, 129–158 (2019)

    MathSciNet  MATH  Google Scholar 

  53. Fan, J.: Comments on ‘Wavelets in statistics: A review’ by A. Antoniadis. J. Ital. Stat. Soc. 6, 131–138 (1997)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. College of Mathematics and Physics, Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Center for Applied Mathematics and Artificial Intelligence, Guangxi University for Nationalities, Nanning, 530006, Guangxi, China

    Peng-Jie Liu, Jin-Bao Jian & Xian-Zhen Jiang

  2. College of Mathematics and Information Science, Guangxi University, Nanning, 530004, Guangxi, China

    Peng-Jie Liu & Bo He

  3. School of Mathematics, China University of Mining and Technology, Xuzhou, 221116, Jiangsu, China

    Peng-Jie Liu

Authors
  1. Peng-Jie Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jin-Bao Jian
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Bo He
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xian-Zhen Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jin-Bao Jian.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

This work was supported by the National Natural Science Foundation of China (No. 12171106) and the Natural Science Foundation of Guangxi Province (Nos. 2020GXNSFDA238017 and 2018GXNSFFA281007).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Liu, PJ., Jian, JB., He, B. et al. Convergence of Bregman Peaceman–Rachford Splitting Method for Nonconvex Nonseparable Optimization. J. Oper. Res. Soc. China 11, 707–733 (2023). https://doi.org/10.1007/s40305-022-00411-x

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s40305-022-00411-x

Keywords

Mathematics Subject Classification

Search

Navigation