IDEAS home Printed from https://ideas.repec.org/a/wsi/apjorx/v34y2017i06ns0217595917500300.html
   My bibliography  Save this article

A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems

Author

Listed:
  • Zhongming Wu

    (School of Economics and Management, Southeast University, Nanjing 211189, P. R. China)

  • Min Li

    (School of Management and Engineering, Nanjing University, Nanjing 210093, P. R. China)

  • David Z. W. Wang

    (School of Civil and Environmental Engineering, Nanyang Technological University, Singapore)

  • Deren Han

    (School of Mathematical Sciences, Jiangsu Key Labratory for NSLSCS, Nanjing Normal University, Nanjing 210023, P. R. China)

Abstract

In this paper, we propose a symmetric alternating method of multipliers for minimizing the sum of two nonconvex functions with linear constraints, which contains the classic alternating direction method of multipliers in the algorithm framework. Based on the powerful Kurdyka–Łojasiewicz property, and under some assumptions about the penalty parameter and objective function, we prove that each bounded sequence generated by the proposed method globally converges to a critical point of the augmented Lagrangian function associated with the given problem. Moreover, we report some preliminary numerical results on solving l1/2 regularized sparsity optimization and nonconvex feasibility problems to indicate the feasibility and effectiveness of the proposed method.

Suggested Citation

  • Zhongming Wu & Min Li & David Z. W. Wang & Deren Han, 2017. "A Symmetric Alternating Direction Method of Multipliers for Separable Nonconvex Minimization Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(06), pages 1-27, December.
  • Handle: RePEc:wsi:apjorx:v:34:y:2017:i:06:n:s0217595917500300
    DOI: 10.1142/S0217595917500300
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0217595917500300
    Download Restriction: Access to full text is restricted to subscribers

    File URL: https://libkey.io/10.1142/S0217595917500300?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hédy Attouch & Jérôme Bolte & Patrick Redont & Antoine Soubeyran, 2010. "Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 438-457, May.
    2. Radu Ioan Boţ & Ernö Robert Csetnek & Szilárd Csaba László, 2016. "An inertial forward–backward algorithm for the minimization of the sum of two nonconvex functions," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(1), pages 3-25, February.
    3. Jonathan Eckstein & Michael C. Ferris, 1998. "Operator-Splitting Methods for Monotone Affine Variational Inequalities, with a Parallel Application to Optimal Control," INFORMS Journal on Computing, INFORMS, vol. 10(2), pages 218-235, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zehui Jia & Xue Gao & Xingju Cai & Deren Han, 2021. "Local Linear Convergence of the Alternating Direction Method of Multipliers for Nonconvex Separable Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 188(1), pages 1-25, January.
    2. Peixuan Li & Yuan Shen & Suhong Jiang & Zehua Liu & Caihua Chen, 2021. "Convergence study on strictly contractive Peaceman–Rachford splitting method for nonseparable convex minimization models with quadratic coupling terms," Computational Optimization and Applications, Springer, vol. 78(1), pages 87-124, January.
    3. Kai Tu & Haibin Zhang & Huan Gao & Junkai Feng, 2020. "A hybrid Bregman alternating direction method of multipliers for the linearly constrained difference-of-convex problems," Journal of Global Optimization, Springer, vol. 76(4), pages 665-693, April.
    4. Min Li & Zhongming Wu, 2019. "Convergence Analysis of the Generalized Splitting Methods for a Class of Nonconvex Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 183(2), pages 535-565, November.
    5. Zhongming Wu & Chongshou Li & Min Li & Andrew Lim, 2021. "Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems," Journal of Global Optimization, Springer, vol. 79(3), pages 617-644, March.
    6. Wu, Tingting & Ng, Michael K. & Zhao, Xi-Le, 2021. "Sparsity reconstruction using nonconvex TGpV-shearlet regularization and constrained projection," Applied Mathematics and Computation, Elsevier, vol. 410(C).
    7. Jing Zhao & Qiao-Li Dong & Michael Th. Rassias & Fenghui Wang, 2022. "Two-step inertial Bregman alternating minimization algorithm for nonconvex and nonsmooth problems," Journal of Global Optimization, Springer, vol. 84(4), pages 941-966, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Xianfu Wang & Ziyuan Wang, 2022. "Malitsky-Tam forward-reflected-backward splitting method for nonconvex minimization problems," Computational Optimization and Applications, Springer, vol. 82(2), pages 441-463, June.
    2. Zhili Ge & Zhongming Wu & Xin Zhang & Qin Ni, 2023. "An extrapolated proximal iteratively reweighted method for nonconvex composite optimization problems," Journal of Global Optimization, Springer, vol. 86(4), pages 821-844, August.
    3. Le Thi Khanh Hien & Duy Nhat Phan & Nicolas Gillis, 2022. "Inertial alternating direction method of multipliers for non-convex non-smooth optimization," Computational Optimization and Applications, Springer, vol. 83(1), pages 247-285, September.
    4. Francesco Rinaldi & Damiano Zeffiro, 2023. "Avoiding bad steps in Frank-Wolfe variants," Computational Optimization and Applications, Springer, vol. 84(1), pages 225-264, January.
    5. Kely D. V. Villacorta & Paulo R. Oliveira & Antoine Soubeyran, 2014. "A Trust-Region Method for Unconstrained Multiobjective Problems with Applications in Satisficing Processes," Journal of Optimization Theory and Applications, Springer, vol. 160(3), pages 865-889, March.
    6. Bo Jiang & Tianyi Lin & Shiqian Ma & Shuzhong Zhang, 2019. "Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis," Computational Optimization and Applications, Springer, vol. 72(1), pages 115-157, January.
    7. Zehui Jia & Jieru Huang & Xingju Cai, 2021. "Proximal-like incremental aggregated gradient method with Bregman distance in weakly convex optimization problems," Journal of Global Optimization, Springer, vol. 80(4), pages 841-864, August.
    8. Glaydston Carvalho Bento & João Xavier Cruz Neto & Antoine Soubeyran & Valdinês Leite Sousa Júnior, 2016. "Dual Descent Methods as Tension Reduction Systems," Journal of Optimization Theory and Applications, Springer, vol. 171(1), pages 209-227, October.
    9. Bolte, Jérôme & Le, Tam & Pauwels, Edouard & Silveti-Falls, Antonio, 2022. "Nonsmooth Implicit Differentiation for Machine Learning and Optimization," TSE Working Papers 22-1314, Toulouse School of Economics (TSE).
    10. Masoud Ahookhosh & Le Thi Khanh Hien & Nicolas Gillis & Panagiotis Patrinos, 2021. "A Block Inertial Bregman Proximal Algorithm for Nonsmooth Nonconvex Problems with Application to Symmetric Nonnegative Matrix Tri-Factorization," Journal of Optimization Theory and Applications, Springer, vol. 190(1), pages 234-258, July.
    11. Alexander Y. Kruger & Nguyen H. Thao, 2015. "Quantitative Characterizations of Regularity Properties of Collections of Sets," Journal of Optimization Theory and Applications, Springer, vol. 164(1), pages 41-67, January.
    12. Jing Zhao & Qiao-Li Dong & Michael Th. Rassias & Fenghui Wang, 2022. "Two-step inertial Bregman alternating minimization algorithm for nonconvex and nonsmooth problems," Journal of Global Optimization, Springer, vol. 84(4), pages 941-966, December.
    13. Fornasier, Massimo & Maly, Johannes & Naumova, Valeriya, 2021. "Robust recovery of low-rank matrices with non-orthogonal sparse decomposition from incomplete measurements," Applied Mathematics and Computation, Elsevier, vol. 392(C).
    14. Emanuel Laude & Peter Ochs & Daniel Cremers, 2020. "Bregman Proximal Mappings and Bregman–Moreau Envelopes Under Relative Prox-Regularity," Journal of Optimization Theory and Applications, Springer, vol. 184(3), pages 724-761, March.
    15. W. Ackooij & S. Demassey & P. Javal & H. Morais & W. Oliveira & B. Swaminathan, 2021. "A bundle method for nonsmooth DC programming with application to chance-constrained problems," Computational Optimization and Applications, Springer, vol. 78(2), pages 451-490, March.
    16. Nguyen Hieu Thao, 2018. "A convergent relaxation of the Douglas–Rachford algorithm," Computational Optimization and Applications, Springer, vol. 70(3), pages 841-863, July.
    17. Jérôme Bolte & Edouard Pauwels, 2016. "Majorization-Minimization Procedures and Convergence of SQP Methods for Semi-Algebraic and Tame Programs," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 442-465, May.
    18. D. Russell Luke & Shoham Sabach & Marc Teboulle & Kobi Zatlawey, 2017. "A simple globally convergent algorithm for the nonsmooth nonconvex single source localization problem," Journal of Global Optimization, Springer, vol. 69(4), pages 889-909, December.
    19. Bian, Fengmiao & Zhang, Xiaoqun, 2021. "A parameterized Douglas–Rachford splitting algorithm for nonconvex optimization," Applied Mathematics and Computation, Elsevier, vol. 410(C).
    20. J. X. Cruz Neto & P. R. Oliveira & P. A. Soares & A. Soubeyran, 2014. "Proximal Point Method on Finslerian Manifolds and the “Effort–Accuracy” Trade-off," Journal of Optimization Theory and Applications, Springer, vol. 162(3), pages 873-891, September.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wsi:apjorx:v:34:y:2017:i:06:n:s0217595917500300. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/apjor/apjor.shtml .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.