×
Bagirov, A. M.; Jin, L.; Karmitsa, N.; Al Nuaimat, A.; Sultanova, N.

Subgradient method for nonconvex nonsmooth optimization. (English) Zbl 1282.90133

J. Optim. Theory Appl. 157, No. 2, 416-435 (2013).
Based on the notion of quasisecants introduced by A. M. Bagirov and A. N. Ganjehlou [Optim. Methods Softw. 25, No. 1, 3–18 (2010; Zbl 1202.65072)], the authors develop a version of the subgradient method for solving nonconvex nonsmooth optimization problems. Quasisecants are subgradients computed in some neighborhood of a point. The method contains a simple procedure for finding descent directions and for solving line search subproblems. The convergence of the method for a broad class of nonconvex nonsmooth optimization problems is proved. The results of numerical experiments demonstrate that this algorithm is a significant improvement of the subgradient method. The comparison of the method with proximal bundle methods are given as well.
Reviewer: Do Van Luu (Hanoi)

Cited in 20 Documents

MSC:

90C26 Nonconvex programming, global optimization
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods

Keywords:

nonsmooth optimization; nonconvex optimization; subgradient method; bundle method; quasisecants

Citations:

Zbl 1202.65072

Software:

NDA; LDGB; QSM; DGM; PNEW
Cite Review PDF
Full Text: DOI

References:

[1] Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, New York (1999) · Zbl 1015.90077
[2] Polyak, B.T.: Introduction to Optimization. Optimization Software, New York (1987) · Zbl 0625.62093
[3] Shor, N.Z.: Minimization Methods for Non-differentiable Functions. Springer, Berlin (1985) · Zbl 0561.90058 · doi:10.1007/978-3-642-82118-9
[4] Anstreicher, K.M., Wolsey, L.A.: Two “well-known” properties of subgradient optimization. Math. Program. 120(1), 213-220 (2009) · Zbl 1180.90179 · doi:10.1007/s10107-007-0148-y
[5] Beltran, C., Heredia, F.J.: An effective line search for the subgradient method. J. Optim. Theory Appl. 125(1), 1-18 (2005) · Zbl 1114.90122 · doi:10.1007/s10957-004-1708-4
[6] Nedić, A., Ozdaglar, A.: Subgradient methods for saddle-point problems. J. Optim. Theory Appl. 142(1), 205-228 (2009) · Zbl 1175.90415 · doi:10.1007/s10957-009-9522-7
[7] 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 · doi:10.1137/070704277
[8] Nesterov, Y.: Primal-dual subgradient methods for convex problems. Math. Program. 120(1), 221-259 (2009) · Zbl 1191.90038 · doi:10.1007/s10107-007-0149-x
[9] Bagirov, A.M., Ganjehlou, A.N.: A quasisecant method for minimizing nonsmooth functions. Optim. Methods Softw. 25(1), 3-18 (2010) · Zbl 1202.65072 · doi:10.1080/10556780903151565
[10] Bagirov, A.M., 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 · doi:10.1007/s10957-007-9335-5
[11] 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 · doi:10.1080/10556780410001648112
[12] 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 · doi:10.1137/S1052623402411459
[13] Hare, W., Sagastizábal, C.: A redistributed proximal bundle method for nonconvex optimization. SIAM J. Optim. 20(5), 2442-2473 (2010) · Zbl 1211.90183 · doi:10.1137/090754595
[14] Kiwiel, K.C.: Methods of Descent for Nondifferentiable Optimization. Springer, Berlin (1985) · Zbl 0561.90059
[15] Mäkelä, M.M., Neittaanmäki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific, Singapore (1992) · Zbl 0757.49017
[16] 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 · doi:10.1137/S1052623496303329
[17] Haarala, M., Miettinen, K., Mäkelä, M.M.: New limited memory bundle method for large-scale nonsmooth optimization. Optim. Methods Softw. 19(6), 673-692 (2004) · Zbl 1068.90101 · doi:10.1080/10556780410001689225
[18] Haarala, N., Miettinen, K., Mäkelä, M.M.: Globally convergent limited memory bundle method for large-scale nonsmooth optimization. Math. Program. 109(1), 181-205 (2007) · Zbl 1278.90451 · doi:10.1007/s10107-006-0728-2
[19] Lukšan, L., Vlček, J.: A bundle-Newton method for nonsmooth unconstrained minimization. Math. Program. 83(1), 373-391 (1998) · Zbl 0920.90132 · doi:10.1007/BF02680566
[20] Bagirov, A., Ganjehlou, A.N.: An approximate subgradient algorithm for unconstrained nonsmooth, onconvex optimization. Math. Methods Oper. Res. 67(2), 187-206 (2008) · Zbl 1155.90014 · doi:10.1007/s00186-007-0186-5
[21] Bagirov, A., Ganjehlou, A.N., Ugon, J., Tor, A.H.: A generalized subgradient method with piecewise linear subproblem. Dyn. Contin. Discrete Impuls. Syst. (B) 17(5), 621-638 (2010) · Zbl 1214.49012
[22] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[23] Demyanov, V.F., Rubinov, A.M.: Constructive Nonsmooth Analysis. Peter Lang, Frankfurt am Main (1995) · Zbl 0887.49014
[24] Lukšan, L., Vlček, J.: Test problems for nonsmooth unconstrained and linearly constrained optimization. Technical report no. 798, Institute of Computer Science, Academy of Sciences of the Czech Republic (2000)
[25] Lukšan, L., Vlček, J.: Algorithm 811: NDA: algorithms for nondifferentiable optimization. ACM Trans. Math. Softw. 27(2), 193-213 (2001) · Zbl 1070.65552 · doi:10.1145/383738.383740
[26] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.