IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v68y2017i3d10.1007_s10898-016-0488-3.html
   My bibliography  Save this article

A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes

Author

Listed:
  • Kaisa Joki

    (University of Turku)

  • Adil M. Bagirov

    (Federation University Australia)

  • Napsu Karmitsa

    (University of Turku)

  • Marko M. Mäkelä

    (University of Turku)

Abstract

In this paper, we develop a version of the bundle method to solve unconstrained difference of convex (DC) programming problems. It is assumed that a DC representation of the objective function is available. Our main idea is to utilize subgradients of both the first and second components in the DC representation. This subgradient information is gathered from some neighborhood of the current iteration point and it is used to build separately an approximation for each component in the DC representation. By combining these approximations we obtain a new nonconvex cutting plane model of the original objective function, which takes into account explicitly both the convex and the concave behavior of the objective function. We design the proximal bundle method for DC programming based on this new approach and prove the convergence of the method to an $$\varepsilon $$ ε -critical point. The algorithm is tested using some academic test problems and the preliminary numerical results have shown the good performance of the new bundle method. An interesting fact is that the new algorithm finds nearly always the global solution in our test problems.

Suggested Citation

  • Kaisa Joki & Adil M. Bagirov & Napsu Karmitsa & Marko M. Mäkelä, 2017. "A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes," Journal of Global Optimization, Springer, vol. 68(3), pages 501-535, July.
    • Handle: RePEc:spr:jglopt:v:68:y:2017:i:3:d:10.1007_s10898-016-0488-3
    DOI: 10.1007/s10898-016-0488-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-016-0488-3
    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-016-0488-3?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. Le An & Pham Tao, 2005. "The DC (Difference of Convex Functions) Programming and DCA Revisited with DC Models of Real World Nonconvex Optimization Problems," Annals of Operations Research, Springer, vol. 133(1), pages 23-46, January.
    2. Pey-Chun Chen & Pierre Hansen & Brigitte Jaumard & Hoang Tuy, 1998. "Solution of the Multisource Weber and Conditional Weber Problems by D.-C. Programming," Operations Research, INFORMS, vol. 46(4), pages 548-562, August.
    3. A. Bagirov & J. Ugon, 2011. "Codifferential method for minimizing nonsmooth DC functions," Journal of Global Optimization, Springer, vol. 50(1), pages 3-22, May.
    4. Hoai Le Thi & Tao Pham Dinh & Huynh Ngai, 2012. "Exact penalty and error bounds in DC programming," Journal of Global Optimization, Springer, vol. 52(3), pages 509-535, March.
    5. Bagirov, Adil M. & Yearwood, John, 2006. "A new nonsmooth optimization algorithm for minimum sum-of-squares clustering problems," European Journal of Operational Research, Elsevier, vol. 170(2), pages 578-596, April.
    6. R. Horst & N. V. Thoai, 1999. "DC Programming: Overview," Journal of Optimization Theory and Applications, Springer, vol. 103(1), pages 1-43, October.
    7. Adil Bagirov & Napsu Karmitsa & Marko M. Mäkelä, 2014. "Introduction to Nonsmooth Optimization," Springer Books, Springer, edition 127, number 978-3-319-08114-4, June.
    8. A. Astorino & A. Fuduli & M. Gaudioso, 2010. "DC models for spherical separation," Journal of Global Optimization, Springer, vol. 48(4), pages 657-669, December.
    9. Annabella Astorino & Antonio Fuduli & Manlio Gaudioso, 2012. "Margin maximization in spherical separation," Computational Optimization and Applications, Springer, vol. 53(2), pages 301-322, October.
    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. Pietro D’Alessandro & Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2024. "The Descent–Ascent Algorithm for DC Programming," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 657-671, March.
    2. Tao Pham Dinh & Van Ngai Huynh & Hoai An Le Thi & Vinh Thanh Ho, 2022. "Alternating DC algorithm for partial DC programming problems," Journal of Global Optimization, Springer, vol. 82(4), pages 897-928, April.
    3. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2023. "Sparse optimization via vector k-norm and DC programming with an application to feature selection for support vector machines," Computational Optimization and Applications, Springer, vol. 86(2), pages 745-766, November.
    4. Najmeh Hoseini Monjezi & S. Nobakhtian, 2019. "A new infeasible proximal bundle algorithm for nonsmooth nonconvex constrained optimization," Computational Optimization and Applications, Springer, vol. 74(2), pages 443-480, November.
    5. M. V. Dolgopolik, 2020. "New global optimality conditions for nonsmooth DC optimization problems," Journal of Global Optimization, Springer, vol. 76(1), pages 25-55, January.
    6. Welington Oliveira, 2019. "Proximal bundle methods for nonsmooth DC programming," Journal of Global Optimization, Springer, vol. 75(2), pages 523-563, October.
    7. Najmeh Hoseini Monjezi & S. Nobakhtian, 2021. "A filter proximal bundle method for nonsmooth nonconvex constrained optimization," Journal of Global Optimization, Springer, vol. 79(1), pages 1-37, January.
    8. Hoai An Le Thi & Vinh Thanh Ho & Tao Pham Dinh, 2019. "A unified DC programming framework and efficient DCA based approaches for large scale batch reinforcement learning," Journal of Global Optimization, Springer, vol. 73(2), pages 279-310, February.
    9. Outi Montonen & Kaisa Joki, 2018. "Bundle-based descent method for nonsmooth multiobjective DC optimization with inequality constraints," Journal of Global Optimization, Springer, vol. 72(3), pages 403-429, November.
    10. Joki, Kaisa & Bagirov, Adil M. & Karmitsa, Napsu & Mäkelä, Marko M. & Taheri, Sona, 2020. "Clusterwise support vector linear regression," European Journal of Operational Research, Elsevier, vol. 287(1), pages 19-35.
    11. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico & Adil M. Bagirov, 2018. "Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations," Journal of Global Optimization, Springer, vol. 71(1), pages 37-55, May.
    12. Wim Ackooij & Welington Oliveira, 2019. "Nonsmooth and Nonconvex Optimization via Approximate Difference-of-Convex Decompositions," Journal of Optimization Theory and Applications, Springer, vol. 182(1), pages 49-80, July.
    13. Welington Oliveira, 2020. "Sequential Difference-of-Convex Programming," Journal of Optimization Theory and Applications, Springer, vol. 186(3), pages 936-959, September.
    14. A. M. Bagirov & N. Hoseini Monjezi & S. Taheri, 2021. "An augmented subgradient method for minimizing nonsmooth DC functions," Computational Optimization and Applications, Springer, vol. 80(2), pages 411-438, November.
    15. Xiaoliang Wang & Liping Pang & Qi Wu & Mingkun Zhang, 2021. "An Adaptive Proximal Bundle Method with Inexact Oracles for a Class of Nonconvex and Nonsmooth Composite Optimization," Mathematics, MDPI, vol. 9(8), pages 1-27, April.

    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. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico & Adil M. Bagirov, 2018. "Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations," Journal of Global Optimization, Springer, vol. 71(1), pages 37-55, May.
    2. A. M. Bagirov & N. Hoseini Monjezi & S. Taheri, 2021. "An augmented subgradient method for minimizing nonsmooth DC functions," Computational Optimization and Applications, Springer, vol. 80(2), pages 411-438, November.
    3. F. Mashkoorzadeh & N. Movahedian & S. Nobakhtian, 2022. "The DTC (difference of tangentially convex functions) programming: optimality conditions," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(2), pages 270-295, July.
    4. Outi Montonen & Kaisa Joki, 2018. "Bundle-based descent method for nonsmooth multiobjective DC optimization with inequality constraints," Journal of Global Optimization, Springer, vol. 72(3), pages 403-429, November.
    5. Liping Pang & Xiaoliang Wang & Fanyun Meng, 2023. "A proximal bundle method for a class of nonconvex nonsmooth composite optimization problems," Journal of Global Optimization, Springer, vol. 86(3), pages 589-620, July.
    6. 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.
    7. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2015. "Optimal Replenishment Order Placement in a Finite Time Horizon," Journal of Optimization Theory and Applications, Springer, vol. 164(3), pages 1078-1089, March.
    8. M. V. Dolgopolik, 2020. "New global optimality conditions for nonsmooth DC optimization problems," Journal of Global Optimization, Springer, vol. 76(1), pages 25-55, January.
    9. Abbaszadehpeivasti, Hadi, 2024. "Performance analysis of optimization methods for machine learning," Other publications TiSEM 3050a62d-1a1f-494e-99ef-7, Tilburg University, School of Economics and Management.
    10. Rafael Blanquero & Emilio Carrizosa & Pierre Hansen, 2009. "Locating Objects in the Plane Using Global Optimization Techniques," Mathematics of Operations Research, INFORMS, vol. 34(4), pages 837-858, November.
    11. Liming Yang & Laisheng Wang, 2013. "A class of semi-supervised support vector machines by DC programming," Advances in Data Analysis and Classification, Springer;German Classification Society - Gesellschaft für Klassifikation (GfKl);Japanese Classification Society (JCS);Classification and Data Analysis Group of the Italian Statistical Society (CLADAG);International Federation of Classification Societies (IFCS), vol. 7(4), pages 417-433, December.
    12. 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.
    13. M. Bierlaire & M. Thémans & N. Zufferey, 2010. "A Heuristic for Nonlinear Global Optimization," INFORMS Journal on Computing, INFORMS, vol. 22(1), pages 59-70, February.
    14. Karmitsa, Napsu & Bagirov, Adil M. & Taheri, Sona, 2017. "New diagonal bundle method for clustering problems in large data sets," European Journal of Operational Research, Elsevier, vol. 263(2), pages 367-379.
    15. Manlio Gaudioso & Giovanni Giallombardo & Giovanna Miglionico, 2020. "Essentials of numerical nonsmooth optimization," 4OR, Springer, vol. 18(1), pages 1-47, March.
    16. Jean-Paul Penot, 2011. "The directional subdifferential of the difference of two convex functions," Journal of Global Optimization, Springer, vol. 49(3), pages 505-519, March.
    17. Annabella Astorino & Antonio Fuduli & Manlio Gaudioso, 2012. "Margin maximization in spherical separation," Computational Optimization and Applications, Springer, vol. 53(2), pages 301-322, October.
    18. Welington Oliveira, 2019. "Proximal bundle methods for nonsmooth DC programming," Journal of Global Optimization, Springer, vol. 75(2), pages 523-563, October.
    19. Hoai An Le Thi & Manh Cuong Nguyen, 2017. "DCA based algorithms for feature selection in multi-class support vector machine," Annals of Operations Research, Springer, vol. 249(1), pages 273-300, February.
    20. David Wozabal, 2012. "A framework for optimization under ambiguity," Annals of Operations Research, Springer, vol. 193(1), pages 21-47, March.

    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:68:y:2017:i:3:d:10.1007_s10898-016-0488-3. 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.