IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v82y2022i2d10.1007_s10898-021-01079-y.html
   My bibliography  Save this article

A unified Douglas–Rachford algorithm for generalized DC programming

Author

Listed:
  • Chih-Sheng Chuang

    (National Chiayi University)

  • Hongjin He

    (Ningbo University)

  • Zhiyuan Zhang

    (Xiamen University)

Abstract

We consider a class of generalized DC (difference-of-convex functions) programming, which refers to the problem of minimizing the sum of two convex (possibly nonsmooth) functions minus one smooth convex part. To efficiently exploit the structure of the problem under consideration, in this paper, we shall introduce a unified Douglas–Rachford method in Hilbert space. As an interesting byproduct of the unified framework, we can easily show that our proposed algorithm is able to deal with convex composite optimization models. Due to the nonconvexity of DC programming, we prove that the proposed method is convergent to a critical point of the problem under some assumptions. Finally, we demonstrate numerically that our proposed algorithm performs better than the state-of-the-art DC algorithm and alternating direction method of multipliers (ADMM) for DC regularized sparse recovery problems.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:jglopt:v:82:y:2022:i:2:d:10.1007_s10898-021-01079-y
    DOI: 10.1007/s10898-021-01079-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-021-01079-y
    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-021-01079-y?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. Minh N. Dao & Matthew K. Tam, 2019. "A Lyapunov-type approach to convergence of the Douglas–Rachford algorithm for a nonconvex setting," Journal of Global Optimization, Springer, vol. 73(1), pages 83-112, January.
    2. Ke Guo & Deren Han, 2018. "A note on the Douglas–Rachford splitting method for optimization problems involving hypoconvex functions," Journal of Global Optimization, Springer, vol. 72(3), pages 431-441, November.
    3. 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.
    4. Francisco Aragón Artacho & Jonathan Borwein, 2013. "Global convergence of a non-convex Douglas–Rachford iteration," Journal of Global Optimization, Springer, vol. 57(3), pages 753-769, November.
    5. 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.
    6. Francisco J. Aragón Artacho & Jonathan M. Borwein & Matthew K. Tam, 2016. "Global behavior of the Douglas–Rachford method for a nonconvex feasibility problem," Journal of Global Optimization, Springer, vol. 65(2), pages 309-327, June.
    7. R. Horst & N. V. Thoai, 1999. "DC Programming: Overview," Journal of Optimization Theory and Applications, Springer, vol. 103(1), pages 1-43, October.
    8. Patrick L. Combettes & Jean-Christophe Pesquet, 2011. "Proximal Splitting Methods in Signal Processing," Springer Optimization and Its Applications, in: Heinz H. Bauschke & Regina S. Burachik & Patrick L. Combettes & Veit Elser & D. Russell Luke & Henry (ed.), Fixed-Point Algorithms for Inverse Problems in Science and Engineering, chapter 0, pages 185-212, Springer.
    9. 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)

    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. Zhongming Wu & Min Li, 2019. "General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems," Computational Optimization and Applications, Springer, vol. 73(1), pages 129-158, May.
    2. Ernest K. Ryu & Yanli Liu & Wotao Yin, 2019. "Douglas–Rachford splitting and ADMM for pathological convex optimization," Computational Optimization and Applications, Springer, vol. 74(3), pages 747-778, December.
    3. 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.
    4. 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.
    5. Francisco J. Aragón Artacho & Rubén Campoy & Matthew K. Tam, 2020. "The Douglas–Rachford algorithm for convex and nonconvex feasibility problems," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 91(2), pages 201-240, April.
    6. 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.
    7. Xiangyu Cui & Xun Li & Duan Li & Yun Shi, 2014. "Time Consistent Behavior Portfolio Policy for Dynamic Mean-Variance Formulation," Papers 1408.6070, arXiv.org, revised Aug 2015.
    8. 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.
    9. Guillaume Sagnol & Edouard Pauwels, 2019. "An unexpected connection between Bayes A-optimal designs and the group lasso," Statistical Papers, Springer, vol. 60(2), pages 565-584, April.
    10. Junhong Lin & Lorenzo Rosasco & Silvia Villa & Ding-Xuan Zhou, 2018. "Modified Fejér sequences and applications," Computational Optimization and Applications, Springer, vol. 71(1), pages 95-113, September.
    11. Nadja Harms & Tim Hoheisel & Christian Kanzow, 2015. "On a Smooth Dual Gap Function for a Class of Player Convex Generalized Nash Equilibrium Problems," Journal of Optimization Theory and Applications, Springer, vol. 166(2), pages 659-685, August.
    12. Francisco J. Aragón Artacho & Rubén Campoy, 2018. "A new projection method for finding the closest point in the intersection of convex sets," Computational Optimization and Applications, Springer, vol. 69(1), pages 99-132, January.
    13. João Carlos O. Souza & Paulo Roberto Oliveira & Antoine Soubeyran, 2016. "Global convergence of a proximal linearized algorithm for difference of convex functions," Post-Print hal-01440298, HAL.
    14. Silvia Bonettini & Peter Ochs & Marco Prato & Simone Rebegoldi, 2023. "An abstract convergence framework with application to inertial inexact forward–backward methods," Computational Optimization and Applications, Springer, vol. 84(2), pages 319-362, March.
    15. Puya Latafat & Panagiotis Patrinos, 2017. "Asymmetric forward–backward–adjoint splitting for solving monotone inclusions involving three operators," Computational Optimization and Applications, Springer, vol. 68(1), pages 57-93, September.
    16. Boglárka G.-Tóth & Kristóf Kovács, 2016. "Solving a Huff-like Stackelberg location problem on networks," Journal of Global Optimization, Springer, vol. 64(2), pages 233-247, February.
    17. Sedi Bartz & Rubén Campoy & Hung M. Phan, 2022. "An Adaptive Alternating Direction Method of Multipliers," Journal of Optimization Theory and Applications, Springer, vol. 195(3), pages 1019-1055, December.
    18. Francisco J. Aragón Artacho & Rubén Campoy & Ilias Kotsireas & Matthew K. Tam, 2018. "A feasibility approach for constructing combinatorial designs of circulant type," Journal of Combinatorial Optimization, Springer, vol. 35(4), pages 1061-1085, May.
    19. Aras Selvi & Aharon Ben-Tal & Ruud Brekelmans & Dick den Hertog, 2022. "Convex Maximization via Adjustable Robust Optimization," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2091-2105, July.
    20. Rafael Blanquero & Emilio Carrizosa & Amaya Nogales-Gómez & Frank Plastria, 2014. "Single-facility huff location problems on networks," Annals of Operations Research, Springer, vol. 222(1), pages 175-195, November.

    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:82:y:2022:i:2:d:10.1007_s10898-021-01079-y. 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.