SavedAdd your journal

Journals / Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics / 2026 / Volume: 71 Issue: 2

Weak subgradient method with path based target level algorithm for nonconvex optimization

Gülçin Dinç Yalçın(ESKISEHIR TECHNICAL UNIVERSİTY)0000-0001-7696-7507
Pages
—
Publication Date
2022-06-30
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

Furthermore, we demonstrate the performance of the proposed method on nonsmooth, nonconvex test problems, and give the computational results by comparing them with the approximately optimal solutions.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:We study a new version of the weak subgradient method, recently developed by Dinc Yalcin and Kasimbeyli for solving nonsmooth, nonconvex problems.
📊
Key Findings & Data:This method is based on the concept of using any weak subgradient of the objective of the problem at the currently generated point with a version of the dynamic stepsize in order to produce a new point at each iteration.
💡
Conclusion & Impact:Furthermore, we demonstrate the performance of the proposed method on nonsmooth, nonconvex test problems, and give the computational results by comparing them with the approximately optimal solutions.
🔬Design:Research Article
📍Scope:Comprehensive Sample
⚙️Variables:Weak subgradient · nonconvex optimization · nonsmooth optimization

Abstract

We study a new version of the weak subgradient method, recently developed by Dinc Yalcin and Kasimbeyli for solving nonsmooth, nonconvex problems. This method is based on the concept of using any weak subgradient of the objective of the problem at the currently generated point with a version of the dynamic stepsize in order to produce a new point at each iteration. The target value needed in the dynamic stepsize is defined using a path based target level (PBTL) algorithm to ensure the optimal value of the problem is reached. We analyze the convergence and give an estimate of the convergence rate of the proposed method. Furthermore, we demonstrate the performance of the proposed method on nonsmooth, nonconvex test problems, and give the computational results by comparing them with the approximately optimal solutions.

🔖

Cite This Article

Yalçın, G. D. (2022). Weak subgradient method with path based target level algorithm for nonconvex optimization. Communications Faculty of Sciences University of Ankara Series A1 Mathematics and Statistics, Volume: 71 Issue: 2. https://doi.org/10.31801/cfsuasmas.826316

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (56)

  1. Akbari, Z., Yousefpour, R., Peyghami, M. R., A new nonsmooth trust region algorithm for locally Lipschitz unconstrained optimization problems, Journal of Optimization Theory and Applications, 164 (3) (2015), 733–754, https://dx.doi.org/10.1007/s10957-014-0534-6
  2. Allen, E., Helgason, R., Kennington, J., Shetty, B., A generalization of Polyak’s convergence result for subgradient optimization, Mathematical Programming, 37 (3) (1987), 309–317.
  3. Azimov, A., Gasimov, R., On weak conjugacy, weak subdifferentials and duality with zero gap in nonconvex optimization, International Journal of Applied Mathematics, 1 (2) (1999), 171–192.
  4. Azimov, A., Gasimov, R., Stability and duality of nonconvex problems via augmented Lagrangian, Cybernetics and Systems Analysis, 38 (3) (2002), 412–421, https://dx.doi.org/10.1023/A:1020316811823
  5. Bagirov, A., A method for minimization of quasidifferentiable functions, Optimization Methods and Software, 17 (1) (2002), 31–60, https://dx.doi.org/10.1080/10556780290027837
  6. Bagirov, A. M., A method for minimizing convex functions based on continuous approximations to the subdifferential, Optimization Methods and Software, 9 (1998), 1–17, https://dx.doi.org/10.1080/10556789808805683
  7. Bagirov, A. M., Ugon, J., Codifferential method for minimizing nonsmooth DC functions, Journal of Global Optimization, 50 (1) (2011), 3–22, https://dx.doi.org/10.1007/s10898-010-9569-x
  8. Beck, A., Teboulle, M., Smoothing and first order methods: A unified framework, SIAM Journal on Optimization, 22 (2) (2012), 557–580, https://dx.doi.org/10.1137/100818327
  9. Bolte, J., Sabach, S., Teboulle, M., Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Mathematical Programming, 146 (1-2) (2014), 459–494, https://dx.doi.org/10.1007/s10107-013-0701-9
  10. Borges, P., Sagastiz´abal, C., Solodov, M., A regularized smoothing method for fully parameterized convex problems with applications to convex and nonconvex two-stage stochastic programming, Mathematical Programming (2020), 1–33, https://dx.doi.org/10.1007/s10107-020-01582-2
  11. Bot¸, R. I., Csetnek, E. R., An inertial Tsengs type proximal algorithm for nonsmooth and nonconvex optimization problems, Journal of Optimization Theory and Applications, 171 (2) (2016), 600–616, https://dx.doi.org/10.1007/s10957-015-0730-z
  12. Bot, R. I., Csetnek, E. R., Nguyen, D. K., A proximal minimization algorithm for structured nonconvex and nonsmooth problems, SIAM Journal on Optimization, 29 (2) (2019), 1300–1328, https://dx.doi.org/10.1137/18M1190689
  13. Bot¸, R. I., Hendrich, C., A variable smoothing algorithm for solving convex optimization problems, TOP, 23 (1) (2015), 124–150, https://dx.doi.org/10.1007/s11750-014-0326-z
  14. Brannlund, U., On Relaxation Methods for Nonsmooth Convex Optimization, PhD thesis, Stockholm: Department of Mathematics, Royal Institute of Technology, 1993.
  15. Burke, J. V., Hoheisel, T., Epi-convergent smoothing with applications to convex composite functions, SIAM Journal on Optimization, 23 (3) (2013), 1457–1479, https://dx.doi.org/10.1137/120889812
  16. Burke, J. V., Lewis, A. S., Overton, M. L., A robust gradient sampling algorithm for nonsmooth, nonconvex optimization, SIAM Journal on Optimization, 15 (3) (2005), 751–779, https://dx.doi.org/10.1137/030601296
  17. Chen, X., Smoothing methods for nonsmooth, nonconvex minimization, Mathematical Programming, 134 (1) (2012), 71–99, https://dx.doi.org/10.1007/s10107-012-0569-0
  18. Clarke, F. H., Optimization and Nonsmooth Analysis, SIAM, 1990.
  19. Curtis, F. E., Que, X., An adaptive gradient sampling algorithm for nonsmooth optimization, Optimization Methods and Software, 28 (6) (2013), 1302–1324, https://dx.doi.org/10.1080/10556788.2012.714781
  20. Curtis, F. E., Que, X., A quasi-Newton algorithm for nonconvex, nonsmooth optimization with global convergence guarantees, Mathematical Programming Computation, 7 (4) (2015), 399–428, https://dx.doi.org/10.1007/s12532-015-0086-2
  21. Dennis, J. E., Li, S. B. B., Tapia, R. A., A unified approach to global convergence of trust region methods for nonsmooth optimization, Mathematical Programming, 68 (1-3) (1995), 319–346, https://dx.doi.org/10.1007/BF01585770
  22. Dinc Yalcin, G., Kasimbeyli, R., Weak subgradient method for solving nonsmooth nonconvex optimization problems, Optimization, 70 (7) (2021), 1513–1553, https://dx.doi.org/10.1080/02331934.2020.1745205
  23. Ermoliev, Y. M., Methods of solution of nonlinear extremal problems, Cybernetics, 2 (4) (1966), 1–14, https://dx.doi.org/10.1007/BF01071403
  24. Fuduli, A., Gaudioso, M., Giallombardo, G., A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization, Optimization Methods and Software, 19 (1) (2004), 89–102, https://dx.doi.org/10.1080/10556780410001648112
  25. Fuduli, A., Gaudioso, M., Giallombardo, G., Minimizing nonconvex nonsmooth functions via cutting planes and proximity control, SIAM Journal on Optimization, 14 (3) (2004), 743–756, https://dx.doi.org/10.1137/S1052623402411459
  26. Gasimov, R. N., Augmented Lagrangian duality and nondifferentiable optimization methods in nonconvex programming, Journal of Global Optimization, 24 (2) (2002), 187–203, https://dx.doi.org/10.1023/A:1020261001771
  27. Goffin, J. L., Kiwiel, K. C., Convergence of a simple subgradient level method, Mathematical Programming, 85 (1) (1999), 207–211, https://dx.doi.org/10.1007/s101070050053
  28. Grothey, A., Decomposition Methods for Nonlinear Nonconvex Optimization Problems, PhD thesis, Citeseer, 2001.
  29. Haarala, M., Miettinen, K., M¨akel¨a, M. M., New limited memory bundle method for largescale nonsmooth optimization, Optimization Methods and Software, 19 (6) (2004), 673–692, https://dx.doi.org/10.1080/10556780410001689225
  30. Haarala, N., Miettinen, K., M¨akel¨a, M. M., Globally convergent limited memory bundle method for large-scale nonsmooth optimization, Mathematical Programming, 109 (1) (2007), 181–205, https://dx.doi.org/10.1007/s10107-006-0728-2
  31. Hoseini, N., Nobakhtian, S., A new trust region method for nonsmooth nonconvex optimization, Optimization, 67 (8) (2018), 1265–1286, https://dx.doi.org/10.1080/02331934.2018.1470175
  32. Hu, Y., Yang, X., Sim, C.-K., Inexact subgradient methods for quasi-convex optimization problems, European Journal of Operational Research, 240 (2) (2015), 315–327, https://dx.doi.org/10.1016/j.ejor.2014.05.017
  33. Kasimbeyli, R., Mammadov, M., On weak subdifferentials, directional derivatives, and radial epiderivatives for nonconvex functions, SIAM Journal on Optimization, 20 (2) (2009), 841– 855, https://dx.doi.org/10.1137/080738106
  34. Kasimbeyli, R., Mammadov, M., Optimality conditions in nonconvex optimization via weak subdifferentials, Nonlinear Analysis: Theory, Methods & Applications, 74 (7) (2011), 2534–2547, https://dx.doi.org/10.1016/j.na.2010.12.008
  35. Kiwiel, K. C., Methods of Decent for Nondifferentiable Optimization, Lecture Notes in Mathematics, No. 1133, Amer Chemical Soc 1155 16TH St, NW, Washington, DC 20036, 1985.
  36. Kiwiel, K. C., Restricted step and Levenberg–Marquardt techniques in proximal bundle methods for nonconvex nondifferentiable optimization, SIAM Journal on Optimization, 6 (1) (1996), 227–249, https://dx.doi.org/10.1137/0806013
  37. Kiwiel, K. C., Convergence and efficiency of subgradient methods for quasiconvex minimization, Mathematical Programming, 90 (1) (2001), 1–25, https://dx.doi.org/10.1007/s101070100198
  38. Kiwiel, K. C., Convergence of approximate and incremental subgradient methods for convex optimization, SIAM Journal on Optimization, 14 (3) (2004), 807–840, https://dx.doi.org/10.1137/S1052623400376366
  39. Kiwiel, K. C., Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization, SIAM Journal on Optimization, 18 (2) (2007), 379–388, https://dx.doi.org/10.1137/050639673
  40. Lewis, A. S., Overton, M. L., Nonsmooth optimization via quasi-Newton methods, Mathematical Programming, 141 (1-2) (2013), 135–163, https://dx.doi.org/10.1007/s10107-012-0514-2
  41. Luksan, L., Vlcek, J., A bundle-Newton method for nonsmooth unconstrained minimization, Mathematical Programming, 83 (1-3) (1998), 373–391, https://dx.doi.org/10.1007/BF02680566
  42. Luksan, L., Vlcek, J., NDA: Algorithms for Nondifferentiable Optimization, Technical Report 797, Institute of Computer Science, Academy of Sciences of the Czech Rebuplic, Prague, 2000.
  43. Luksan, L., Vlcek, J., Ramesova, N., UFO 2002, Interactive System for Universal Functional Optimization, Technicka Zprava 883, 2002.
  44. Makela, M. M., N. P., Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control, World Scientific, 1992.
  45. Nedic, A., Bertsekas, D. P., Incremental subgradient methods for nondifferentiable optimization, SIAM Journal on Optimization, 12 (1) (2001), 109–138, https://dx.doi.org/10.1137/S1052623499362111
  46. Nedic, A., Bertsekas, D. P., The effect of deterministic noise in subgradient methods, Mathematical Programming, 125 (1) (2010), 75–99, https://dx.doi.org/10.1007/s10107-008-0262-5
  47. Nesterov, Y., Smooth minimization of non-smooth functions, Mathematical Programming, 103 (1) (2005), 127–152, https://dx.doi.org/10.1007/s10107-004-0552-5
  48. Pock, T., Sabach, S., Inertial proximal alternating linearized minimization (ipalm) for nonconvex and nonsmooth problems, SIAM Journal on Imaging Sciences, 9 (4) (2016), 1756–1787, https://dx.doi.org/10.1137/16M1064064
  49. Polak, E., Mayne, D. Q., Higgins, J. E., Superlinearly convergent algorithm for minmax problems, Journal of Optimization Theory and Applications, 69 (3) (1991), 407–439, https://dx.doi.org/10.1007/BF00940683
  50. Polyak, B. T., A general method for solving extremal problems, Doklady Akademii Nauk, Russian Academy of Sciences, 174 (1) (1967), 33–36.
  51. Polyak, B. T., Minimization of unsmooth functionals, USSR Computational Mathematics and Mathematical Physics, 9 (3) (1969), 14–29, https://dx.doi.org/10.1016/0041-5553(69)90061-5
  52. Qi, L., Sun, J., A trust region algorithm for minimization of locally Lipschitzian functions, Mathematical Programming, 66 (1-3) (1994), 25–43, https://dx.doi.org/10.1007/BF01581136
  53. Shor, N. Z., Minimization Methods for Non-differentiable Functions (K. Kiwiel and A. Ruszcynski,translate), Heidelberg:Springer-Verlag Berlin, 1985.
  54. Tran-Dinh, Q., Adaptive smoothing algorithms for nonsmooth composite convex minimization, Computational Optimization and Applications, 66 (3) (2017), 425–451, https://dx.doi.org/10.1007/s10589-016-9873-6
  55. Vlcek, J., Luksan, L., Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization, Journal of Optimization Theory and Applications, 111 (2) (2001), 407–430, https://dx.doi.org/10.1023/A:1011990503369
  56. Zhang, P., Bao, G., Path-based incremental target level algorithm on riemannian manifolds, Optimization, 69 (4) (2020), 799–819, https://dx.doi.org/10.1080/02331934.2019.1671840