A stabilized simulated annealing-based Barzilai–Borwein method for the solution of unconstrained optimization problems

Document Type : Research Article

Authors

• H. Sharma
• R.K. Nayak

Department of Mathematics, International Institute of Information Technology, Bhubaneswar, Odisha, India, 751029.

10.22067/ijnao.2024.86481.1379

Abstract

The Barzilai–Borwein method offers efficient step sizes for large-scale un-constrained optimization problems. However, it may not guarantee global convergence for nonquadratic objective functions. Simulated annealing-based on Barzilai–Borwein (SABB) method addresses this issue by in-corporating a simulated annealing rule. This work proposes a novel step-size strategy for the SABB method, referred to as the SABBm method. Furthermore, we introduce two stabilized variants: SABBstab and SABBmstab. SABBstab combines a simulated annealing rule with a sta-bilization step to ensure convergence. SABBmstab builds upon SABBstab, incorporating the modified step size derived from the SABBm method. The effectiveness and competitiveness of the proposed methods are demon-strated through numerical experiments on CUTEr benchmark problems.

Keywords

• Unconstrained optimization
• Barzilai–Borwein method
• Simu-lated annealing method
• Stabilized BB method

Main Subjects

• Optimization

---

References

[1] Akaike, H. On a successive transformation of probability distribution and its application to the analysis of the optimum gradient method, Annals of the Institute of Statistical Mathematics 11(1) (1959), 1–16.
[2] Andrei, N. An unconstrained optimization test functions collection, Adv. Model. Optim. 10(1) (2008), 147–161.
[3] Barzilai, J. and Borwein, J.M. Two-point step size gradient methods, IMA J. Numer. Anal. 8(1) (1988), 141–148.
[4] Birgin, E.G., Martínez, J.M. and Raydan, M. Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim. 10(4) (2000), 1196–1211.
[5] Burdakov, Y., Dai, O. and Huang, N. Stabilized Barzilai–Borwein method, J. Comput. Math. 37(6) (2019), 916–936.
[6] Cauchy, A. Méthode générale pour la résolution des systemes d’équations simultanées, Comp. Rend. Sci. Paris 25 (1847), 536–538.

[7] Dai, Y.-H. and Liao, L.-Z. R-linear convergence of the barzilai and bor-wein gradient method, IMA J. Numer. Anal. 22(1) (2002), 1–10.
[8] Dai, Y.-H. and Zhang, H. Adaptive two-point stepsize gradient algorithm, Numer. Algorithms 27 (2001), 377–385.
[9] Dolan, E.D. and Moré, J.J. Benchmarking optimization software with performance profiles, Math. Program. 91(2) (2002), 201–213.
[10] Dong, W.-L., Li, X. and Peng, Z. A simulated annealing-based Barzilai–Borwein gradient method for unconstrained optimization problems, Asia-Pac. J. Oper. Res. 36(04) (2019), 1950017.
[11] Fletcher, R. Low storage methods for unconstrained optimization, Dundee Department of Mathematics and Computer Science, University of Dundee, 1988.
[12] Gould, N.I.M., Orban, D. and Toint, P.L. Cutest: a constrained and unconstrained testing environment with safe threads for mathematical optimization, Comput. Optim. Appl. 60(3) (2015), 545–557.
[13] Grippo, L., Lampariello, F. and Lucidi, S. A nonmonotone line search technique for newton’s method, SIAM J. Numer. Anal. 23(4) (1986) 707–716.
[14] Han, J. and Liu, G. Global convergence analysis of a new nonmonotone BFGS algorithm on convex objective functions, Comput. Optim. Appl. 7 (1997), 277–289.
[15] Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. Optimization by simulated annealing, Science, 220(4598) (1983), 671–680.
[16] Liu, G.H. and Peng, J.M. The convergence properties of a nonmonotonic algorithm, J. Comput. Math. 1 (1992), 65–71.
[17] Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H. and Teller, E. Equation of state calculations by fast computing machines, J. Comput. Math. 21(6) (1953), 1087–1092.

[18] Mu, X. and Liu, W. An augmented lagrangian method for binary quadratic programming based on a class of continuous functions, Op-tim. Lett. 10(3) (2016), 485–497.
[19] Nocedal, J. and Wright, S.J. Numerical optimization, Springer, 1999.
[20] Raydan, M. On the barzilai and borwein choice of steplength for the gradient method, IMA J. Numer. Anal. 13(3) (1993), 321–326.
[21] Raydan, M. The barzilai and borwein gradient method for the large scale unconstrained minimization problem, SIAM J. Optim. 7(1) (1997), 26–33.
[22] Toint, P.L. An assessment of nonmonotone linesearch techniques for unconstrained optimization, SIAM J. Sci. Comput. 17(3) (1996), 725–739.
[23] Wang, C., Liu, Q. and Yang, X. Convergence properties of nonmono-tone spectral projected gradient methods, J. Comput. Appl. Math. 182(1) (2005), 51–66.
[24] Zhang, H. and Hager, W.W. A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optim. 14(4) (2004), 1043–1056.
[25] Zhensheng, Yu. Solving bound constrained optimization via a new non-monotone spectral projected gradient method, Appl. Numer. Math. 58(9) (2008), 1340–1348.
[26] Zhou, J.L. and Tits, A.L. Nonmonotone line search for minimax prob-lems, J. Optim. Theory Appl. 76(3) (1993), 455–476.