Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization

Hong Seng Sim; Chuei Yee Chen; Wah June Leong; Jiao Li

doi:10.3934/jimo.2021143

Article Contents

2022, Volume 18, Issue 6: 3975-3988. Doi: 10.3934/jimo.2021143

This issue Previous Article Coordinated optimization of production scheduling and maintenance activities with machine reliability deterioration Next Article A best possible algorithm for an online scheduling problem with position-based learning effect

Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization

1.
Centre for Mathematical Sciences, Universiti Tunku Abdul Rahman, 43000 Kajang, Malaysia
2.
Department of Mathematics and Statistics, Faculty of Science, Universiti Putra Malaysia, 43400 UPM Serdang, Malaysia
3.
Institute for Mathematical Research, Universiti Putra Malaysia, 43400 UPM Serdang, Malaysia
4.
School of Mathematics and Statistics, Changsha University of Science and Technology, Changsha, Hunan 410114, China

^* Corresponding author: cychen@upm.edu.my
^* Corresponding author: cychen@upm.edu.my

Received: February 28, 2021

Revised: April 30, 2021

Early access: August 2021

Published: September 2022

The first author was supported by UTAR Research Fund IPSR/RMC/UTARRF/2019-C1/S02

Abstract Full Text(HTML) Figure(5) Related Papers Cited by

Abstract

This paper proposes a nonmonotone spectral gradient method for solving large-scale unconstrained optimization problems. The spectral parameter is derived from the eigenvalues of an optimally sized memoryless symmetric rank-one matrix obtained under the measure defined as a ratio of the determinant of updating matrix over its largest eigenvalue. Coupled with a nonmonotone line search strategy where backtracking-type line search is applied selectively, the spectral parameter acts as a stepsize during iterations when no line search is performed and as a milder form of quasi-Newton update when backtracking line search is employed. Convergence properties of the proposed method are established for uniformly convex functions. Extensive numerical experiments are conducted and the results indicate that our proposed spectral gradient method outperforms some standard conjugate-gradient methods.

Keywords:

Mathematics Subject Classification: Primary: 65K10; Secondary: 90C06.

Citation:

Full Text(HTML)

Figure 1. SG-mSR1 vs BB in terms of function values.

Download: Full-size image PowerPoint slide

Figure 2. SG-mSR1 vs BB in terms of gradient norm.

Download: Full-size image PowerPoint slide

Figure 3. Performance profile comparing the efficiency of SG-mSR1 methods and the standard CG methods in terms of number of iterations

Download: Full-size image PowerPoint slide

Figure 4. Performance profile comparing the efficiency of SG-mSR1 methods and the standard CG methods in terms of number of function calls

Download: Full-size image PowerPoint slide

Figure 5. Performance profile comparing the efficiency of SG-mSR1 methods and the standard CG methods in terms of CPU time

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	N. Andrei, An unconstrained optimization test functions collection, Adv. Model. Optim., 10 (2008), 147-161.
[2]	J. Barzilai and J. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141-148.
[3]	I. Bongartz, A. R. Conn, N. I. M. Gould and P. L. Toint, CUTE: Constrained and unconstrained testing environment, ACM Transactions on Mathematical Software, 21 (1995), 123-160. doi: 10.1145/200979.201043.
[4]	R. H. Byrd and J. Nocedal, A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. Numer. Anal., 26 (1989), 727-739. doi: 10.1137/0726042.
[5]	A. Cauchy, Methodes generales pour la resolution des syst'emes dequations simultanees, Comp. Rend. Sci. Paris, 25 (1847), 536-538.
[6]	Y. H. Dai and Y. X. Yuan, A nonlinear conjugate gradient method with a strong global convergence property, SIAM J. Optim., 10 (1999), 177-182. doi: 10.1137/S1052623497318992.
[7]	J. E. Dennis and H. Wolkowicz, Sizing and least change secant methods, SIAM J. Numer. Anal., 30 (1993), 1291-1314. doi: 10.1137/0730067.
[8]	E. D. Dolan and J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201-213. doi: 10.1007/s101070100263.
[9]	R. Fletcher, Practical Methods of Optimization: Unconstrained Optimization, 2$^{nd}$ edition, A Wiley-Interscience Publication. John Wiley & Sons, Ltd., Chichester, 1987.
[10]	R. Fletcher and C. Reeves, Function minimization by conjugate gradients, Comput. J., 7 (1964), 149-154.
[11]	W. Glunt, T. L. Hayden and M. Raydan, Molecular conformations from distance matrices, Journal of Computational Chemistry, 14 (1993), 114-120. doi: 10.1002/jcc.540140115.
[12]	L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search techniques for Newton's method, SIAM J. Numer. Anal., 23 (1986), 707-716. doi: 10.1137/0723046.
[13]	W. W. Hager and H. Zhang, A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM J. Optim., 16 (2005), 170-192. doi: 10.1137/030601880.
[14]	C. M. Ip and M. J. Todd, Optimal conditioning and convergence in rank one quasi-Newton updates, SIAM J. Numer. Anal., 25 (1988), 206-221. doi: 10.1137/0725015.
[15]	W. La Cruz, J. Martinez and M. M. Raydan, Spectral residual method without gradient information for solving large-scale nonlinear systems of equations, Math. Comp., 75 (2006), 1429-1448. doi: 10.1090/S0025-5718-06-01840-0.
[16]	W. La Cruz and M. Raydan, Nonmonotone spectral methods for large-scale nonlinear systems, Optim. Methods Softw., 18 (2003), 583-599. doi: 10.1080/10556780310001610493.
[17]	W. J. Leong and M. A. Hassan, A restarting approach for the symmetric rank one update for unconstrained optimization, Comput. Optim. Appl., 42 (2009), 327-334. doi: 10.1007/s10589-007-9115-z.
[18]	D. C. Liu and J. Nocedal, On the limited memory BFGS method for large scale optimization, Math. Programming, 45 (1989), 503-528. doi: 10.1007/BF01589116.
[19]	Y. Liu and C. Storey, Efficient generalized conjugate gradient algorithms, Part I: Theory, J. Optim. Theory Appl., 69 (1991), 129-137. doi: 10.1007/BF00940464.
[20]	F. Luengo, M. Raydan, W. Glunt and T. L. Hayden, Preconditioned spectral gradient method, Numer. Algorithms, 30 (2002), 241-258. doi: 10.1023/A:1020181927999.
[21]	E. Polak and G. Ribiére, Note sur la convergence de directions conjugées, Rev. Francaise Informat Recherche Opertionelle, 3e Année, 16 (1969), 35-43.
[22]	B. T. Polyak, The conjugate gradient method in extreme problems, USSR Computational Mathematics and Mathematical Physics, 9 (1969), 94-112.
[23]	M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM Journal on Optimization, 7 (1997), 26-33. doi: 10.1137/S1052623494266365.
[24]	H. S. Sim, W. J. Leong and C. Y. Chen, Gradient method with multiple damping for large-scale unconstrained optimization, Optim. Lett., 13 (2019), 617-632. doi: 10.1007/s11590-018-1247-9.
[25]	H. S. Sim, W. J. Leong, C. Y. Chen and S. N. I. Ibrahim, Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization, Numer. Algebra Control Optim., 8 (2018), 387-397. doi: 10.3934/naco.2018024.
[26]	H. Wolkowicz, Measure for symmetric rank-one updates, Math. Oper. Res., 19 (1994), 815-830. doi: 10.1287/moor.19.4.815.