An augmented subgradient method for minimizing nonsmooth DC functions | Computational Optimization and Applications Skip to main content
Springer Nature Link
Log in

An augmented subgradient method for minimizing nonsmooth DC functions

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

A method, called an augmented subgradient method, is developed to solve unconstrained nonsmooth difference of convex (DC) optimization problems. At each iteration of this method search directions are found by using several subgradients of the first DC component and one subgradient of the second DC component of the objective function. The developed method applies an Armijo-type line search procedure to find the next iteration point. It is proved that the sequence of points generated by the method converges to a critical point of the unconstrained DC optimization problem. The performance of the method is demonstrated using academic test problems with nonsmooth DC objective functions and its performance is compared with that of two general nonsmooth optimization solvers and five solvers specifically designed for unconstrained DC optimization. Computational results show that the developed method is efficient and robust for solving nonsmooth DC optimization problems.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Artacho, F.J.A., Campoy, R., Vuong, P.T.: Using positive spanning sets to achieve d-stationarity with the boosted DC algorithm. Vietnam J. Math. 48(2), 363–376 (2020)

    Article  MathSciNet  Google Scholar 

  2. Artacho, F.J.A., Fleming, R.M.T., Vuong, P.T.: Accelerating the DC algorithm for smooth functions. Math. Program. 169, 95–118 (2018)

    Article  MathSciNet  Google Scholar 

  3. Artacho, F.J.A., Vuong, P.T.: The boosted difference of convex functions algorithm for nonsmooth functions. SIAM J. Optim. 30(1), 980–1006 (2020)

    Article  MathSciNet  Google Scholar 

  4. An, L.T.H., Tao, P.D., Ngai, H.V.: Exact penalty and error bounds in DC programming. J. Glob. Optim. 52(3), 509–535 (2012)

    Article  MathSciNet  Google Scholar 

  5. An, L.T.H., Tao, P.D.: The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133, 23–46 (2005)

    Article  MathSciNet  Google Scholar 

  6. Astorino, A., Fuduli, A., Gaudioso, M.: DC models for spherical separation. J. Glob. Optim. 48(4), 657–669 (2010)

    Article  MathSciNet  Google Scholar 

  7. Bagirov, A.M., Gaudioso, M., Karmitsa, N., Mäkelä, M.M., Taheri, S. (eds.): Numerical Nonsmooth Optimization: State of the Art Algorithms. Springer, Berlin (2020)

    MATH  Google Scholar 

  8. Bagirov, A.M., Karmitsa, N., Mäkelä, M.M.: Introduction to Nonsmooth Optimization: Theory, Practice and Software. Springer, New York (2014)

    Book  Google Scholar 

  9. Bagirov, A.M., Taheri, S., Joki, K., Karmitsa, N., Mäkelä, M.M.: Aggregate subgradient method for nonsmooth DC optimization. Optim. Lett. 15(1), 83–96 (2020)

    Article  MathSciNet  Google Scholar 

  10. Bagirov, A.M., Taheri, S., Cimen, E.: Incremental DC optimization algorithm for large-scale clusterwise linear regression. J. Comput. Appl. Math. 389, 113323 (2021)

    Article  MathSciNet  Google Scholar 

  11. Bagirov, A.M., Taheri, S., Ugon, J.: Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems. Pattern Recognit. 53, 12–24 (2016)

    Article  Google Scholar 

  12. Bagirov, A.M., Ugon, J.: Nonsmooth DC programming approach to clusterwise linear regression: optimality conditions and algorithms. Optim. Methods Softw. 33(1), 194–219 (2018)

    Article  MathSciNet  Google Scholar 

  13. Bagirov, A.M., Ugon, J.: Codifferential method for minimizing nonsmooth DC functions. J. Glob. Optim. 50, 3–22 (2011)

    Article  MathSciNet  Google Scholar 

  14. Burke, J.V., Lewis, A.S., Overton, M.L.: A robust gradient sampling algorithm for nonsmooth, nonconvex optimization. SIAM J. Optim. 15(3), 751–779 (2005)

    Article  MathSciNet  Google Scholar 

  15. Demyanov, V.F., Rubinov, A.M.: Constructive Nonsmooth Analysis. Peter Lang, Frankfurt a. M. (1995)

    MATH  Google Scholar 

  16. Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)

    Article  MathSciNet  Google Scholar 

  17. de Oliveira, W.: Proximal bundle methods for nonsmooth DC programming. J. Glob. Optim. 75, 523–563 (2019)

    Article  MathSciNet  Google Scholar 

  18. de Oliveira, W.: Sequential difference-of-convex programming. J. Optim. Theory Appl. 186(3), 936–959 (2020)

    Article  MathSciNet  Google Scholar 

  19. de Oliveira, W.: The ABC of DC programming. Set-Valued Var. Anal. 28, 679–706 (2020)

    Article  MathSciNet  Google Scholar 

  20. de Oliveira, W., Tcheou, M.P.: An inertial algorithm for DC programming. Set-Valued Var. Anal. 27, 895–919 (2019)

    Article  MathSciNet  Google Scholar 

  21. Frangioni, A.: Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res. 21, 1099–1118 (1996)

    Article  MathSciNet  Google Scholar 

  22. Gaudioso, M., Giallombardo, G., Miglionico, G., Bagirov, A.M.: Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations. J. Glob. Optim. 71(1), 37–55 (2018)

    Article  MathSciNet  Google Scholar 

  23. Horst, R., Thoai, N.V.: DC programming: overview. J. Optim. Theory Appl. 103, 1–43 (1999)

    Article  MathSciNet  Google Scholar 

  24. Joki, K., Bagirov, A.M., Karmitsa, N., Mäkelä, M.M.: A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes. J. Glob. Optim. 68, 501–535 (2017)

    Article  MathSciNet  Google Scholar 

  25. Joki, K., Bagirov, A.M., Karmitsa, N., Mäkelä, M.M., Taheri, S.: Double bundle method for finding Clarke stationary points in nonsmooth DC programming. SIAM J. Optim. 28(2), 1892–1919 (2018)

    Article  MathSciNet  Google Scholar 

  26. Joki, K., Bagirov, A.M., Karmitsa, N., Mäkelä, M.M., Taheri, S.: Double bundle method for finding Clarke stationary points in nonsmooth DC optimization. Technical reports 1173, Turku Center for Computer Science (TUCS), Turku (2017)

  27. Khalaf, W., Astorino, A., D’Alessandro, P., Gaudioso, M.: A DC optimization-based clustering technique for edge detection. Optim. Lett. 11(3), 627–640 (2017)

  28. Lewis, A.S., Overton, M.L.: Nonsmooth optimization via quasi-Newton methods. Math. Program. 141(1–2), 135–163 (2013)

    Article  MathSciNet  Google Scholar 

  29. Luksan, L.: Dual method for solving a special problem of quadratic programming as a subproblem at linearly constrained nonlinear minimax approximation. Kybernetika 20(6), 445–457 (1984)

    MathSciNet  MATH  Google Scholar 

  30. Mäkelä, M.M.: Multiobjective proximal bundle method for nonconvex nonsmooth optimization: Fortran subroutine MPBNGC 2.0. Reports of the Department of Mathematical Information Technology, Series B. Scientific Computing B 13/2003, University of Jyväskylä, Jyväskylä (2003)

  31. Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific Publishing Co., Singapore (1992)

    Book  Google Scholar 

  32. Ordin, B., Bagirov, A.M.: A heuristic algorithm for solving the minimum sum-of-squares clustering problems. J. Glob. Optim. 61, 341–361 (2015)

    Article  MathSciNet  Google Scholar 

  33. Pang, J.S., Razaviyayn, M., Alvarado, A.: Computing B-stationary points of nonsmooth DC programs. Math. Oper. Res. 42(1), 95–118 (2017)

    Article  MathSciNet  Google Scholar 

  34. Sun, W.Y., Sampaio, R.J.B., Candido, M.A.B.: Proximal point algorithm for minimization of DC functions. J. Comput. Math. 21(4), 451–462 (2003)

    MathSciNet  MATH  Google Scholar 

  35. Tao, P.D., Souad, E.B.: Algorithms for solving a class of nonconvex optimization problems: methods of subgradient. North-Holland Mathematics Studies. Fermat Days 85: Mathematics for Optimization. 129, 249–271 (1986)

  36. Toland, J.F.: On subdifferential calculus and duality in nonconvex optimization. Bull. Soc. Math. France Mémoire. 60, 177–183 (1979)

    Article  MathSciNet  Google Scholar 

  37. Tuy, H.: Convex Analysis and Global Optimization. Kluwer, Dordrecht (1998)

    Book  Google Scholar 

  38. van Ackooij, W., de Oliveira, W.: Nonsmooth and nonconvex optimization via approximate difference-of-convex decompositions. J. Optim. Theory Appl. 182, 49–80 (2019)

    Article  MathSciNet  Google Scholar 

  39. Wolfe, P.: Finding the nearest point in a polytope. Math. Program. 11, 128–149 (1976)

    Article  MathSciNet  Google Scholar 

  40. Zaffaroni, A.: Continuous approximations, codifferentiable functions and minimization methods. In: Demyanov, V.F., Rubinov, A.M. (eds.) Nonconvex Optimization and Its Applications, pp. 361–391. Kluwer Academic Publishers, Dordrecht, Quasidifferentiability and Related Topics (2000)

Download references

Acknowledgements

The research by Dr. A.M. Bagirov is supported by the Australian Government through the Australian Research Council’s Discovery Projects funding scheme (Project No. DP190100580) and the research by Dr. N. Hoseini Monjezi is supported by the National Elite Foundation of Iran. The authors would like to thank the handling editor and three anonymous referees for their comments that helped to improve the quality of the paper.

Author information

Authors and Affiliations

  1. School of Engineering, Information Technology and Physical Sciences, Federation University Australia, Ballarat, Australia

    A. M. Bagirov

  2. Department of Applied Mathematics and Computer Science, Faculty of Mathematics and Statistics, University of Isfahan, Isfahan, Iran

    N. Hoseini Monjezi

  3. School of Science, RMIT University, Melbourne, Australia

    S. Taheri

Authors
  1. A. M. Bagirov
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. N. Hoseini Monjezi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. S. Taheri
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. Taheri.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bagirov, A.M., Hoseini Monjezi, N. & Taheri, S. An augmented subgradient method for minimizing nonsmooth DC functions. Comput Optim Appl 80, 411–438 (2021). https://doi.org/10.1007/s10589-021-00304-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-021-00304-4

Keywords

Mathematics Subject Classification

Search

Navigation