×

zbMATH — the first resource for mathematics

Aggregate subgradient method for nonsmooth DC optimization. (English) Zbl 1460.90140
Summary: The aggregate subgradient method is developed for solving unconstrained nonsmooth difference of convex (DC) optimization problems. The proposed method shares some similarities with both the subgradient and the bundle methods. Aggregate subgradients are defined as a convex combination of subgradients computed at null steps between two serious steps. At each iteration search directions are found using only two subgradients: the aggregate subgradient and a subgradient computed at the current null step. It is proved that the proposed method converges to a critical point of the DC optimization problem and also that the number of null steps between two serious steps is finite. The new method is tested using some academic test problems and compared with several other nonsmooth DC optimization solvers.
MSC:
90C26 Nonconvex programming, global optimization
Software:
LDGB; SolvOpt; PNEW; DGM; QSM
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anstreicher, KM; Wolsey, LA, Two well-known properties of subgradient optimization, Math. Program., 120, 1, 213-220 (2009) · Zbl 1180.90179
[2] Bagirov, AM; Ganjehlou, AN, A quasisecant method for minimizing nonsmooth functions, Optim. Methods Softw., 25, 1, 3-18 (2010) · Zbl 1202.65072
[3] Bagirov, AM; Jin, L.; Karmitsa, N.; Al Nuaimat, A.; Sultanova, N., Subgradient method for nonconvex nonsmooth optimization, J. Optim. Theory Appl., 157, 2, 416-435 (2013) · Zbl 1282.90133
[4] Bagirov, AM; Karasözen, B.; Sezer, M., Discrete gradient method: Derivative-free method for nonsmooth optimization, J. Optim. Theory Appl., 137, 2, 317-334 (2008) · Zbl 1165.90021
[5] Bagirov, AM; Karmitsa, N.; Mäkelä, MM, Introduction to Nonsmooth Optimization: Theory, Practice and Software (2014), New York: Springer, New York · Zbl 1312.90053
[6] Bagirov, A.M., Taheri, S., Bai, F., Wu, Z.: An approximate ADMM for solving linearly constrained nonsmooth optimization problems with two blocks of variables. In: International Series in Numerical Mathematics (2019) · Zbl 1419.90082
[7] Bagirov, A.M., Taheri, S., Joki, K., Karmitsa, N., Mäkelä, M.M.: A new subgradient based method for nonsmooth DC programming, TUCS. Tech. Rep., No. 1201, Turku Centre for Computer Science, Turku (2019) · Zbl 1401.90170
[8] Bagirov, AM; Taheri, S.; Ugon, J., Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems, Pattern Recognit., 53, 12-24 (2016) · Zbl 1412.68200
[9] Bagirov, AM; Ugon, J., Codifferential method for minimizing nonsmooth DC functions, J. Global Optim., 50, 1, 3-22 (2011) · Zbl 1242.90172
[10] Beltran, C.; Heredia, FJ, An effective line search for the subgradient method, J. Optim. Theory Appl., 125, 1, 1-18 (2005) · Zbl 1114.90122
[11] Bertsekas, DP, Nonlinear Programming (1999), New York: Athena Scientific, New York · Zbl 1015.90077
[12] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Mathematical Programming, 91, 2, 201-213 (2002) · Zbl 1049.90004
[13] Fuduli, A.; Gaudioso, M.; Giallombardo, G., A DC piecewise affine model and a bundling technique in nonconvex nonsmooth minimization, Optim. Methods Softw., 19, 1, 89-102 (2004) · Zbl 1211.90182
[14] Fuduli, A.; Gaudioso, M.; Giallombardo, G., Minimizing nonconvex nonsmooth functions via cutting planes and proximity control, SIAM J. Optim., 14, 3, 743-756 (2004) · Zbl 1079.90105
[15] Gaudioso, M.; Giallombardo, G.; Miglionico, G.; Bagirov, AM, Minimizing nonsmooth DC functions via successive DC piecewise-affine approximations, J. Global Optim., 71, 1, 37-55 (2018) · Zbl 1418.90201
[16] Haarala, M.; Miettinen, K.; Mäkelä, MM, New limited memory bundle method for large-scale nonsmooth optimization, Optim. Methods Softw., 19, 6, 673-692 (2004) · Zbl 1068.90101
[17] Haarala, N.; Miettinen, K.; Mäkelä, MM, Globally convergent limited memory bundle method for large-scale nonsmooth optimization, Math. Program., 109, 1, 181-205 (2007) · Zbl 1278.90451
[18] Hare, W.; Sagastizábal, C., A redistributed proximal bundle method for nonconvex optimization, SIAM J. Optim., 20, 5, 2442-2473 (2010) · Zbl 1211.90183
[19] Joki, K.; Bagirov, AM; Karmitsa, N.; Mäkelä, MM, A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes, J. Global Optim., 68, 501-535 (2017) · Zbl 1369.90137
[20] Joki, K., Bagirov, A.M., Karmitsa, N., Mäkelä, M.M., Taheri, S.: Double bundle method for nonsmooth DC optimization, TUCS. Tech. Rep., No. 1173, Turku Centre for Computer Science, Turku (2017) · Zbl 1369.90137
[21] Joki, K.; Bagirov, AM; Karmitsa, N.; Mäkelä, MM; Taheri, S., Double bundle method for finding Clarke stationary points in nonsmooth DC programming, SIAM J. Optim., 28, 2, 1892-1919 (2018) · Zbl 1401.90170
[22] Kappel, F.; Kuntsevich, AV, An implementation of Shor’s \(r\)-algorithm, Comput. Optim. Appl., 15, 2, 193-205 (2000) · Zbl 0947.90112
[23] Kiwiel, KC, Methods of Descent for Nondifferentiable Optimization (1985), Berlin: Springer, Berlin · Zbl 0561.90059
[24] Le Thi Hoai, A.; Pham Dinh, T., Solving a class of linearly constrained indefinite quadratic problems by D.C. algorithms, J. Global Optim., 11, 253-285 (1997) · Zbl 0905.90131
[25] Le Thi Hoai, A.; Pham Dinh, T., The DC (differnece of convex functions) programming and DCA revised with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133, 1-4, 23-46 (2005) · Zbl 1116.90122
[26] Lukšan, L.; Vlček, J., A bundle-Newton method for nonsmooth unconstrained minimization, Math. Program., 83, 1, 373-391 (1998) · Zbl 0920.90132
[27] Mäkelä, MM; Neittaanmäki, P., Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control (1992), Singapore: World Scientific, Singapore
[28] Mifflin, R.; Sun, D.; Qi, L., Quasi-Newton bundle-type methods for nondifferentiable convex optimization, SIAM J. Optim., 8, 2, 583-603 (1998) · Zbl 0927.65074
[29] Nemirovski, A.; Juditsky, A.; Lan, G.; Shapiro, A., Robust stochastic approximation approach to stochastic programming, SIAM J. Optim., 19, 4, 1574-1609 (2009) · Zbl 1189.90109
[30] Nesterov, Y., Primal-dual subgradient methods for convex problems, Math. Program., 120, 1, 221-259 (2009) · Zbl 1191.90038
[31] Polyak, BT, Introduction to Optimization (1987), New York: Optimization Software Inc., New York · Zbl 0708.90083
[32] Shor, NZ, Minimization Methods for Non-differentiable Functions (1985), Berlin: Springer, Berlin
[33] Souza, JCO; Oliveira, PR; Soubeyran, A., Global convergence of a proximal linearized algorithm for difference of convex functions, Optim. Lett., 10, 1529-1539 (2016) · Zbl 1355.90073
[34] Strekalovsky, AS, Global optimality conditions for nonconvex optimization, J. Global Optim., 12, 415-434 (1998) · Zbl 0908.90243
[35] Tuy, H., Convex Analysis and Global Optimization (1998), Dordrescht: Kluwer Academic Publishers, Dordrescht · Zbl 0904.90156
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.