×

zbMATH — the first resource for mathematics

On the convergence rate of scaled gradient projection method. (English) Zbl 1414.90333
Summary: The scaled gradient projection (SGP) method, which can be viewed as a promising improvement of the classical gradient projection method, is a quite efficient solver for real-world problems arising in image science and machine learning. Most recently, S. Bonettini and M. Prato [Inverse Probl. 31, No. 9, Article ID 095008, 20 p. (2015; Zbl 1333.90124)] proved that the SGP method with the monotone Armijo line search technique has the \(\mathcal O (1/k)\) convergence rate, where \(k\) counts the iteration. In this paper, we first show that the SGP method could be equipped with the nonmonotone line search procedure proposed by H. Zhang and W. W. Hager [SIAM J. Optim. 14, No. 4, 1043–1056 (2004; Zbl 1073.90024)]. To some extent, such a nonmonotone technique might improve the performance of SGP method, because its effectiveness has been verified for unconstrained optimization by comparing with the traditional monotone and nonmonotone strategies. Then, we prove that the new SGP method also has the \(\mathcal O (1/k)\) convergence rate under the condition that the objective function is convex. Furthermore, we derive the linear convergence of the SGP algorithm under the strongly convexity assumption of the involved objective function.
MSC:
90C30 Nonlinear programming
90C52 Methods of reduced gradient type
Software:
TRON; CONV_QP; GPDT
PDF BibTeX Cite
Full Text: DOI
References:
[1] Bardsley, JM; Nagy, JG, Covariance-preconditioned iterative methods for nonnegatively constrained astronomical imaging, SIAM J Matrix Anal Appl, 27, 1184-1197, (2006) · Zbl 1102.65044
[2] Bertero, M.; Lantéri, H.; Zanni, L.; Censor, Y.; Jiang, M.; Louis, AK, Mathematical methods in biomedical imaging and intensity-modulated radiation therapy (IMRT), Iterative image reconstruction: a point of view, 37-63, (2008), Pisa: Birkhauser, Pisa
[3] Boyd, S.; Parikh, N.; Chu, E., Distributed optimization and statistical learning via the alternating direction method of multipliers, Found Trends Mach Learn, 3, 1-122, (2010) · Zbl 1229.90122
[4] Figueiredo, M.; Nowak, R.; Wright, S., Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems, IEEE J Sel Top Sign Proces, 1, 586-598, (2007)
[5] Lin, CJ, Projected gradient methods for nonnegative matrix factorization, Neural Comput, 19, 2756-2779, (2007) · Zbl 1173.90583
[6] Serafini, T.; Zanghirati, G.; Zanni, L., Gradient projection methods for quadratic programs and applications in trainning support vector machines, Optim Method Softw, 20, 353-378, (2005) · Zbl 1072.90026
[7] Serafini, T.; Zanni, L., On the working set selection in gradient projection-based decomposition techniques for support vector machines, Optim Method Softw, 20, 583-596, (2005) · Zbl 1116.90115
[8] Zanni, L., An improved gradient projection-based decomposition technique for support vector machines, Comput Manage Sci, 3, 131-145, (2006) · Zbl 1163.90693
[9] Beck, A.; Teboulle, M., Smoothing and first order methods: a unified framework, SIAM J Optim, 22, 557-580, (2012) · Zbl 1251.90304
[10] Bertsimas, D.; Freund, RM; Sun, XA, An accelerated first order method for solving SOS relaxations of unconstrained polynomial optimization problems, Optim Method Softw, 28, 424-441, (2013) · Zbl 1273.90198
[11] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search technique for Newton’s method, SIAM J Numer Anal, 23, 707-716, (1986) · Zbl 0616.65067
[12] Fountoulakis, K.; Gondzio, J., A second-order method for strongly convex l_{1} regularization problems, Math Program Ser A, 156, 189-219, (2016) · Zbl 1364.90255
[13] Lin, CJ; Jorge, J., Newton’s method for large bound-constrained optimization problems, SIAM J Optim, 9, 1100-1127, (1999) · Zbl 0957.65064
[14] Chambolle, A.; Pock, T., A first-order primal-dual algorithm for convex problems with applications to imaging, J Math Imaging Vis, 40, 120-145, (2011) · Zbl 1255.68217
[15] Devolder, O.; Glineur, F.; Nesterov, Y., First order methods of smooth convex optimization with inexact oracle, Math Program Ser. A, 146, 37-75, (2014) · Zbl 1317.90196
[16] Nesterov, Y.; Nemirovski, A., On first order algorithms for l1 nuclear norm minimization, Act Num, 22, 509-575, (2013) · Zbl 1293.65089
[17] Shi, LY; Ansari, QH; Wen, CF, Incremental gradient projection algorithm for constrained composite minimization problems, J Nonlinear Var Anal, 1, 253-264, (2017) · Zbl 1398.90205
[18] Qin, X.; Yao, JC, Projection splitting algorithms for nonself operators, J Nonlinear Convex Anal, 18, 925-935, (2017) · Zbl 06847101
[19] Liu, Y., A modified hybrid method for solving variational inequality problems in Banach spaces, J Nonlinear Funct Anal, 2017, (2017)
[20] Birgin, E.; Martinez, J.; Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM J Optim, 10, 1196-1211, (2000) · Zbl 1047.90077
[21] Birgin, E.; Martinez, J.; Raydan, M., Spectral projected gradient methods: review and perspectives, J Stat Softw, 60, 539-559, (2014)
[22] Dai, Y.; Fletcher, R., Projected Barzilai–Borwein methods for large-scale box-constrained quadratic programming, Numer Math, 100, 21-47, (2005) · Zbl 1068.65073
[23] Dai, Y.; Zhang, HC, Adaptive two-point stepsize gradient algorithm, Numer Alg, 27, 377-385, (2001) · Zbl 0992.65063
[24] Huang, Y.; Liu, H., On the rate of convergence of projected Barzilai-Borwein methods, Optim Method Softw, 30, 880-892, (2015) · Zbl 1338.90300
[25] Huang, Y.; Liu, H., Smoothing projected Barzilai-Borwein method for constrained non-Lipschitz optimization, Comput Optim Appl, 65, 671-698, (2016) · Zbl 1357.90117
[26] Barzilai, J.; Borwein, J., Two-point step size gradient methods, IMA J Numer Anal, 8, 141-148, (1988) · Zbl 0638.65055
[27] Armijo, L., Minimization of functions having Lipschitz continuous first partial derivatives, Pac J Math, 16, 1-3, (1966) · Zbl 0202.46105
[28] Grippo, L.; Lampariello, F.; Lucidi, S., A truncated Newton method with nonmonotone line search for unconstrained optimization, J Optim Theory Appl, 60, 401-419, (1989) · Zbl 0632.90059
[29] Zhang, H.; Hager, W., A nonmonotone line search technique and its application to unconstrained optimization, SIAM J Optim, 14, 1043-1056, (2004) · Zbl 1073.90024
[30] Toint, PL, An assessment of non-monotone line search techniques for unconstrained optimization, SIAM J Sci Comput, 17, 725-739, (1996) · Zbl 0849.90113
[31] Dai, YH, On the nonmonotone line search, J Optim Theory Appl, 112, 315-330, (2002) · Zbl 1049.90087
[32] Dai, YH, A nonmonotone conjugate gradient algorithm for unconstrained optimization, J Syst Sci Complex, 15, 139-145, (2002) · Zbl 1019.90039
[33] Bonettini, S.; Zanella, R.; Zanni, L., A scaled gradient projection method for constrained image deblurring, Inverse Probl, 25, 015002, (2009) · Zbl 1155.94011
[34] Bonettini, S.; Prato, M., New convergence results for the scaled gradient projection method, Inverse Probl, 31, 095008, (2015) · Zbl 1333.90124
[35] Bertsekas, D.; Tsitsiklis, J., Parallel and distributed computation, numerical methods, (1989), Englewood Cliffs (NJ): Prentice-Hall, Englewood Cliffs (NJ) · Zbl 0743.65107
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.