IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v76y2020i4d10.1007_s10898-019-00828-4.html
   My bibliography  Save this article

A hybrid Bregman alternating direction method of multipliers for the linearly constrained difference-of-convex problems

Author

Listed:
  • Kai Tu

    (Beijing University of Technology)

  • Haibin Zhang

    (Beijing University of Technology)

  • Huan Gao

    (Hunan First Normal University)

  • Junkai Feng

    (Beijing University of Technology)

Abstract

In this paper, we propose a hybrid Bregman alternating direction method of multipliers for solving the linearly constrained difference-of-convex problems whose objective can be written as the sum of a smooth convex function with Lipschitz gradient, a proper closed convex function and a continuous concave function. At each iteration, we choose either subgradient step or proximal step to evaluate the concave part. Moreover, the extrapolation technique was utilized to compute the nonsmooth convex part. We prove that the sequence generated by the proposed method converges to a critical point of the considered problem under the assumption that the potential function is a Kurdyka–Łojasiewicz function. One notable advantage of the proposed method is that the convergence can be guaranteed without the Lischitz continuity of the gradient function of concave part. Preliminary numerical experiments show the efficiency of the proposed method.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jglopt:v:76:y:2020:i:4:d:10.1007_s10898-019-00828-4
    DOI: 10.1007/s10898-019-00828-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-019-00828-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-019-00828-4?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. Zhaosong Lu & Xiaorui Li, 2018. "Sparse Recovery via Partial Regularization: Models, Theory, and Algorithms," Mathematics of Operations Research, INFORMS, vol. 43(4), pages 1290-1316, November.
    2. Kristian Bredies & Dirk A. Lorenz & Stefan Reiterer, 2015. "Minimization of Non-smooth, Non-convex Functionals by Iterative Thresholding," Journal of Optimization Theory and Applications, Springer, vol. 165(1), pages 78-112, April.
    3. W. Geremew & N. M. Nam & A. Semenov & V. Boginski & E. Pasiliao, 2018. "A DC programming approach for solving multicast network design problems via the Nesterov smoothing technique," Journal of Global Optimization, Springer, vol. 72(4), pages 705-729, December.
    4. J. Souza & P. Oliveira, 2015. "A proximal point algorithm for DC fuctions on Hadamard manifolds," Journal of Global Optimization, Springer, vol. 63(4), pages 797-810, December.
    5. Tianxiang Liu & Ting Kei Pong & Akiko Takeda, 2019. "A refined convergence analysis of $$\hbox {pDCA}_{e}$$ pDCA e with applications to simultaneous sparse recovery and outlier detection," Computational Optimization and Applications, Springer, vol. 73(1), pages 69-100, May.
    6. 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.
    7. Bo Wen & Xiaojun Chen & Ting Kei Pong, 2018. "A proximal difference-of-convex algorithm with extrapolation," Computational Optimization and Applications, Springer, vol. 69(2), pages 297-324, March.
    8. Chenxi Chen & Yunmei Chen & Yuyuan Ouyang & Eduardo Pasiliao, 2018. "Stochastic Accelerated Alternating Direction Method of Multipliers with Importance Sampling," Journal of Optimization Theory and Applications, Springer, vol. 179(2), pages 676-695, November.
    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. Shota Takahashi & Mituhiro Fukuda & Mirai Tanaka, 2022. "New Bregman proximal type algorithms for solving DC optimization problems," Computational Optimization and Applications, Springer, vol. 83(3), pages 893-931, 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. Hongbo Dong & Min Tao, 2021. "On the Linear Convergence to Weak/Standard d-Stationary Points of DCA-Based Algorithms for Structured Nonsmooth DC Programming," Journal of Optimization Theory and Applications, Springer, vol. 189(1), pages 190-220, April.
    2. Chih-Sheng Chuang & Hongjin He & Zhiyuan Zhang, 2022. "A unified Douglas–Rachford algorithm for generalized DC programming," Journal of Global Optimization, Springer, vol. 82(2), pages 331-349, February.
    3. Yldenilson Torres Almeida & João Xavier Cruz Neto & Paulo Roberto Oliveira & João Carlos de Oliveira Souza, 2020. "A modified proximal point method for DC functions on Hadamard manifolds," Computational Optimization and Applications, Springer, vol. 76(3), pages 649-673, July.
    4. Min Tao & Jiang-Ning Li, 2023. "Error Bound and Isocost Imply Linear Convergence of DCA-Based Algorithms to D-Stationarity," Journal of Optimization Theory and Applications, Springer, vol. 197(1), pages 205-232, April.
    5. J. X. Cruz Neto & P. R. Oliveira & A. Soubeyran & J. C. O. Souza, 2020. "A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problem," Annals of Operations Research, Springer, vol. 289(2), pages 313-339, June.
    6. 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.
    7. Glaydston C. Bento & Orizon P. Ferreira & Jefferson G. Melo, 2017. "Iteration-Complexity of Gradient, Subgradient and Proximal Point Methods on Riemannian Manifolds," Journal of Optimization Theory and Applications, Springer, vol. 173(2), pages 548-562, May.
    8. Peng, Bo & Xu, Hong-Kun, 2020. "Proximal methods for reweighted lQ-regularization of sparse signal recovery," Applied Mathematics and Computation, Elsevier, vol. 386(C).
    9. 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).
    10. 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.
    11. 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.
    12. Daria Ghilli & Karl Kunisch, 2019. "On a Monotone Scheme for Nonconvex Nonsmooth Optimization with Applications to Fracture Mechanics," Journal of Optimization Theory and Applications, Springer, vol. 183(2), pages 609-641, November.
    13. Glaydston Carvalho Bento & Sandro Dimy Barbosa Bitar & João Xavier Cruz Neto & Antoine Soubeyran & João Carlos Oliveira Souza, 2020. "A proximal point method for difference of convex functions in multi-objective optimization with application to group dynamic problems," Computational Optimization and Applications, Springer, vol. 75(1), pages 263-290, January.
    14. Hao Jiang & Daniel P. Robinson & René Vidal & Chong You, 2018. "A nonconvex formulation for low rank subspace clustering: algorithms and convergence analysis," Computational Optimization and Applications, Springer, vol. 70(2), pages 395-418, June.
    15. Weiwei Kong & Renato D. C. Monteiro, 2022. "Accelerated inexact composite gradient methods for nonconvex spectral optimization problems," Computational Optimization and Applications, Springer, vol. 82(3), pages 673-715, July.
    16. 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.
    17. Peiran Yu & Ting Kei Pong, 2019. "Iteratively reweighted $$\ell _1$$ ℓ 1 algorithms with extrapolation," Computational Optimization and Applications, Springer, vol. 73(2), pages 353-386, June.
    18. Daria Ghilli & Karl Kunisch, 2019. "On monotone and primal-dual active set schemes for $$\ell ^p$$ ℓ p -type problems, $$p \in (0,1]$$ p ∈ ( 0 , 1 ]," Computational Optimization and Applications, Springer, vol. 72(1), pages 45-85, January.
    19. Yaohua Hu & Chong Li & Kaiwen Meng & Xiaoqi Yang, 2021. "Linear convergence of inexact descent method and inexact proximal gradient algorithms for lower-order regularization problems," Journal of Global Optimization, Springer, vol. 79(4), pages 853-883, April.
    20. João S. Andrade & Jurandir de O. Lopes & João Carlos de O. Souza, 2023. "An inertial proximal point method for difference of maximal monotone vector fields in Hadamard manifolds," Journal of Global Optimization, Springer, vol. 85(4), pages 941-968, April.

    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:spr:jglopt:v:76:y:2020:i:4:d:10.1007_s10898-019-00828-4. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.