×

A limited memory \(q\)-BFGS algorithm for unconstrained optimization problems. (English) Zbl 1475.65040

Summary: A limited memory \(q\)-BFGS (Broyden-Fletcher-Goldfarb-Shanno) method is presented for solving unconstrained optimization problems. It is derived from a modified BFGS-type update using \(q\)-derivative (quantum derivative). The use of Jackson’s derivative is an effective mechanism for escaping from local minima. The \(q\)-gradient method is complemented to generate the parameter \(q\) for computing the step length in such a way that the search process gradually shifts from global in the beginning to almost local search in the end. Further, the global convergence is established under Armijo-Wolfe conditions even if the objective function is not convex. The numerical experiments show that proposed method is potentially efficient.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C53 Methods of quasi-Newton type

Software:

tn; L-BFGS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Mishra, S.K., Ram, B.: Steepest descent method. In: Introduction to Unconstrained Optimization with R, pp. 131-173, Springer, Singapore (2019)
[2] Mishra, S.K., Ram, B.: Newton’s method. In: Introduction to Unconstrained Optimization with R, pp. 175-209, Springer, Singapore (2019)
[3] Mishra, S.K., Ram, B.: Quasi-Newton methods. In: Introduction to Unconstrained Optimization with R, pp. 245-289, Springer, Singapore (2019)
[4] Mishra S.K., Ram B.: Conjugate gradient methods. In: Introduction to Unconstrained Optimization with R, pp. 211-244, Springer, Singapore (2019) · Zbl 1527.90225
[5] Akaike, H., On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method, Ann. Inst. Stat. Math., 11, 1-17 (1959) · Zbl 0100.14002
[6] Nash, SG, A survey of truncated-Newton methods, J. Comput. Appl. Math., 124, 45-59 (2000) · Zbl 0969.65054
[7] Byrd, RH; Nocedal, J., A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM J. Numer. Anal., 26, 727-739 (1989) · Zbl 0676.65061
[8] Dennis, JE; Moré, JJ, A characterization of superlinear convergence and its application to quasi Newton methods, Math. Comput., 28, 549-560 (1974) · Zbl 0282.65042
[9] Powell, M.J.D.: Some convergence properties of a variable mertric algorithm for minimization without exact line search. In: Cottle, R.W., Lemke, C.E. (eds.) Nonlinear Programming, SIAM-AMS Proceedings, vol. IX, pp. 53-72. SIAM, Philadelphia (1976) · Zbl 0338.65038
[10] Nocedal, J., Updating quasi-Newton matrices with limited storage, Math. Comput., 35, 773-782 (1980) · Zbl 0464.65037
[11] Perry, J.M.: A Class of Conjugate Gradient Algorithms with a Two-Step Variable-Metric Memory. Discussion Paper 269, Center for Mathematical Studies in Economics and Management Science, Northwestern University, Evanston, IL (1977)
[12] Xiao, Y.; Wei, Z.; Wang, Z., A limited memory BFGS-type method for large-scale unconstrained optimization, Comput. Math. Appl., 56, 1001-1009 (2008) · Zbl 1155.90441
[13] Li, DH; Fukushima, M., A modified BFGS method and its global convergence in nonconvex minimization, J. Comput. Appl. Math., 129, 15-35 (2001) · Zbl 0984.65055
[14] Xiao, YH; Li, TF; Wei, ZX, Global convergence of a modified limited memory BFGS method for non-convex minimization, Acta Math. Appl. Sin. Engl. Ser., 29, 555-566 (2013) · Zbl 1303.65048
[15] Shi, Z.; Yang, G.; Xiao, Y., A limited memory BFGS algorithm for non-convex minimization with applications in matrix largest eigenvalue problem, Math. Method Oper. Res., 83, 243-264 (2016) · Zbl 1336.90088
[16] Jackson, FH, On q-definite integrals, Q. J. Pure Appl. Math., 41, 193-203 (1910) · JFM 41.0317.04
[17] Jackson, FH, q-difference equations, Am. J. Math., 32, 305-314 (1910) · JFM 41.0502.01
[18] Andrews, G.E.: q-Series: Their Development and Applications in Analysis, Number Theory, Combinatorics, Physics and Computer Algebra. CBMS Regional Conference Series in Mathematics, vol. 66. American Mathematical Society, Providence, RI (1986) · Zbl 0594.33001
[19] Stanković, MS; Rajković, PM; Marinković, SD, Fractional integrals and derivatives in q-calculus, Appl. Anal. Discrete Math., 1, 311-323 (2007) · Zbl 1199.33013
[20] Zhou, H.; Alzabut, J.; Rezapour, S.; Samei, ME, Uniform persistence and almost periodic solutions of a non-autonomous patch occupancy model, Adv. Differ. Equ., 2020, 143 (2020) · Zbl 1482.34166
[21] Annaby, MH; Mansour, ZS, q-Fractional Calculus and Equations (2012), Heidelberg: Springer, Heidelberg · Zbl 1267.26001
[22] Samei, ME, Existence of solutions for a system of singular sum fractional q-differential equations via quantum calculus, Adv. Diff. Equ., 2020, 23 (2020) · Zbl 1487.34038
[23] Ntouyas, SK; Samei, ME, Existence and uniqueness of solutions for multi-term fractional q-integro-differential equations via quantum calculus, Adv. Differ. Equ., 2019, 475 (2019) · Zbl 1487.34033
[24] Bohner, M.; Peterson, A., Dynamic Equations on Time Scales (2001), Boston: Birkhäuser, Boston · Zbl 0978.39001
[25] Liang, S.; Samei, ME, New approach to solutions of a class of singular fractional q-differential problem via quantum calculus, Adv. Differ. Equ., 2019, 14 (2020) · Zbl 1487.34022
[26] Kalvandi, V.; Samei, ME, New stability results for a sum-type fractional q-integro-differential equation, J. Adv. Math. Stud., 12, 201-209 (2019) · Zbl 1441.45007
[27] Hedayati, V.; Samei, ME, Positive solutions of fractional differential equation with two pieces in chain interval and simultaneous Dirichlet boundary conditions, Bound. Value Probl., 2019, 141 (2019) · Zbl 1513.34111
[28] Samei, ME; Yang, W., Existence of solutions for k-dimensional system of multi-term fractional q-integro-differential equations under anti-periodic boundary conditions via quantum calculus, Math. Methods Appl. Sci., 43, 4360-4382 (2020) · Zbl 1463.39007
[29] Ernst, T.: The history of q-calculus and a new method (Licentiate Thesis). U.U.D.M, Report (2000)
[30] Ernst, T., A method for q-calculus, J. Nonlinear Math. Phys., 10, 487-525 (2003) · Zbl 1041.33013
[31] Bettaibi, N.; Mezlini, K., On the use Of the q-Mellin transform to solve some q-heat and q-wave equations, Int. J. Math. Arch., 3, 446-55 (2012)
[32] Sterroni, A.C., Galski, R.L., Ramos, F.M.: The q-gradient vector for unconstrained continuous optimization problems. In: Hu, B., Morasch, K., Pickl, S., Siegle, M. (eds.) Operations Research Proceedings, pp. 365-370. Springer, Heidelberg, Germany (2010) · Zbl 1421.90165
[33] Gouv \({{\hat{e}}}\) a, E.J.C., Regis, R.G., Soterroni, A.C., Scarabello, M.C., Ramos, F.M.: Global optimization using q-gradients. Eur. J. Oper. Res. 251, 727-738 (2016) · Zbl 1346.90679
[34] Lai, K.K., Mishra, S.K., Ram, B.: A q-conjugate gradient algorithm for unconstrained optimization problems. Pac. J. Optim, Communicated (2020)
[35] Chakraborty, S.K., Panda, G.: q-Line search scheme for optimization problem (2017). arXiv preprint arXiv:1702.01518
[36] Chakraborty, S.K., Panda, G.: Newton like line search method using q-calculus. In: Giri, D., Mohapatra, R.N., Begehr, H., Obaidat, M. (eds.) International Conference on Mathematics and Computing. Communications in Computer and Information Science, vol. 655, pp. 196-208. Springer, Singapore (2017) · Zbl 1442.65109
[37] Al-Saggaf, UM; Moinuddin, M.; Arif, M.; Zerguine, A., The q-least mean squares algorithm, Signal Process., 111, 50-60 (2015)
[38] Ahmed, A.; Moinuddin, M.; Al-Saggaf, UM, q-State space least mean family of algorithms, Circuits Syst. Signal Process., 37, 729-751 (2018) · Zbl 1427.93280
[39] Ablinger, J., Uncu, A.K.: q-Functions—a Mathematica package for q-series and partition theory applications (2019). arXiv preprint arXiv:1910.12410
[40] Rajković, P.; Stanković, M.; Marinković, DS, Mean value theorems in q-calculus, Matematicki vesnik, 54, 171-178 (2002) · Zbl 1058.39018
[41] Rajković, PM; Marinković, SD; Stanković, MS, On q-Newton-Kantorovich method for solving systems of equations, Appl. Math. Comput., 168, 1432-1448 (2005) · Zbl 1081.65045
[42] Li, DH; Fukushima, M., On the global convergence of the BFGS method for nonconvex unconstrained problems, SIAM J. Optim., 11, 1054-1064 (2001) · Zbl 1010.90079
[43] Shi, Z.; Yang, G.; Xiao, Y., A limited memory BFGS algorithm for non-convex minimization with applications in matrix largest eigenvalue problem, Math. Methods Oper. Res., 83, 243-264 (2016) · Zbl 1336.90088
[44] Andrei, N., An unconstrained optimization test functions collection, Adv. Model. Optim., 10, 147-161 (2008) · Zbl 1161.90486
[45] Dolan, ED; Morè, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213 (2002) · Zbl 1049.90004
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.