Year: 2019
Author: Oleg Burdakov, Yuhong Dai, Na Huang
Journal of Computational Mathematics, Vol. 37 (2019), Iss. 6 : pp. 916–936
Abstract
The Barzilai-Borwein (BB) method is a popular and efficient tool for solving large-scale unconstrained optimization problems. Its search direction is the same as the steepest descent (Cauchy) method, but its step size rule is different. Owing to this, it converges much faster than the Cauchy method. A feature of the BB method is that it may generate too long steps, which throw the iterates too far away from the solution. Moreover, it may not converge, even when the objective function is strongly convex. In this paper, a stabilization technique is introduced. It consists in bounding the distance between each pair of successive iterates, which often allows for decreasing the number of BB iterations. When the BB method does not converge, our simple modification of this method makes it convergent. For strongly convex functions with Lipschits gradients, we prove its global convergence, despite the fact that no line search is involved, and only gradient values are used. Since the number of stabilization steps is proved to be finite, the stabilized version inherits the fast local convergence of the BB method. The presented results of extensive numerical experiments show that our stabilization technique often allows the BB method to solve problems in a fewer iterations, or even to solve problems where the latter fails.
You do not have full access to this article.
Already a Subscriber? Sign in as an individual or via your institution
Journal Article Details
Publisher Name: Global Science Press
Language: English
DOI: https://doi.org/10.4208/jcm.1911-m2019-0171
Journal of Computational Mathematics, Vol. 37 (2019), Iss. 6 : pp. 916–936
Published online: 2019-01
AMS Subject Headings:
Copyright: COPYRIGHT: © Global Science Press
Pages: 21
Keywords: Unconstrained optimization Spectral algorithms Stabilization Convergence analysis.
Author Details
-
Two-level optimization approach with accelerated proximal gradient for objective measures in sparse speech reconstruction
Dam, Hai Huyen | Low, Siow Yong | Nordholm, SvenJournal of Industrial and Management Optimization, Vol. 18 (2022), Iss. 5 P.3701
https://doi.org/10.3934/jimo.2021131 [Citations: 1] -
Delayed Weighted Gradient Method with simultaneous step-sizes for strongly convex optimization
Lara, Hugo | Aleixo, Rafael | Oviedo, HarryComputational Optimization and Applications, Vol. 89 (2024), Iss. 1 P.151
https://doi.org/10.1007/s10589-024-00586-4 [Citations: 0] -
A survey of first order stochastic optimization methods and algorithms based adaptive learning rate from a machine learning perspective
Weijuan, Shi | Shuib, Adibah | Alwadood, ZuraidaWOMEN IN PHYSICS: 7th IUPAP International Conference on Women in Physics, (2023), P.040011
https://doi.org/10.1063/5.0177172 [Citations: 0] -
Adaptive learning rate optimization algorithms with dynamic bound based on Barzilai-Borwein method
Wang, Zhi-Jun | Gao, He-Bei | Wang, Xiang-Hong | Zhao, Shuai-Ye | Li, Hong | Zhang, Xiao-QinInformation Sciences, Vol. 634 (2023), Iss. P.42
https://doi.org/10.1016/j.ins.2023.03.050 [Citations: 12] -
A novel stepsize for gradient descent method
Hoai, Pham Thi | Vinh, Nguyen The | Chung, Nguyen Phung HaiOperations Research Letters, Vol. 53 (2024), Iss. P.107072
https://doi.org/10.1016/j.orl.2024.107072 [Citations: 2] -
Latest developments in node-based shape optimization using Vertex Morphing parameterization
Antonau, Ihar | Warnakulasuriya, Suneth | Bletzinger, Kai-Uwe | Bluhm, Fabio Michael | Hojjat, Majid | Wüchner, RolandStructural and Multidisciplinary Optimization, Vol. 65 (2022), Iss. 7
https://doi.org/10.1007/s00158-022-03279-w [Citations: 8] -
On R-linear convergence analysis for a class of gradient methods
Huang, Na
Computational Optimization and Applications, Vol. 81 (2022), Iss. 1 P.161
https://doi.org/10.1007/s10589-021-00333-z [Citations: 2] -
Adjoint-based control of three dimensional Stokes droplets
Fikl, Alexandru | Bodony, Daniel J.Journal of Computational Physics, Vol. 494 (2023), Iss. P.112532
https://doi.org/10.1016/j.jcp.2023.112532 [Citations: 1] -
A family of Barzilai-Borwein steplengths from the viewpoint of scaled total least squares
Li, Shiru | Zhang, Tao | Xia, YongComputational Optimization and Applications, Vol. 87 (2024), Iss. 3 P.1011
https://doi.org/10.1007/s10589-023-00546-4 [Citations: 0] -
Adaptive learning rate algorithms based on the improved Barzilai–Borwein method
Wang, Zhi-Jun | Li, Hong | Xu, Zhou-Xiang | Zhao, Shuai-Ye | Wang, Peng-Jun | Gao, He-BeiPattern Recognition, Vol. 160 (2025), Iss. P.111179
https://doi.org/10.1016/j.patcog.2024.111179 [Citations: 0] -
Boundary element method for the elastic contact problem with hydrostatic load at the contact interface
Huang, De | Yan, Xiang | Larsson, Roland | Almqvist, AndreasApplied Surface Science Advances, Vol. 6 (2021), Iss. P.100176
https://doi.org/10.1016/j.apsadv.2021.100176 [Citations: 5] -
A structured L-BFGS method and its application to inverse problems
Mannel, Florian | Om Aggrawal, Hari | Modersitzki, JanInverse Problems, Vol. 40 (2024), Iss. 4 P.045022
https://doi.org/10.1088/1361-6420/ad2c31 [Citations: 2] -
On the step size selection in variance-reduced algorithm for nonconvex optimization
Yang, Zhuang
Expert Systems with Applications, Vol. 169 (2021), Iss. P.114336
https://doi.org/10.1016/j.eswa.2020.114336 [Citations: 10] -
Achieving geometric convergence for distributed optimization with Barzilai-Borwein step sizes
Gao, Juan | Liu, Xin-Wei | Dai, Yu-Hong | Huang, Yakui | Yang, PengScience China Information Sciences, Vol. 65 (2022), Iss. 4
https://doi.org/10.1007/s11432-020-3256-x [Citations: 7] -
Adjoint-based optimal control of contractile elastic bodies. Application to limbless locomotion on frictional substrates
Bijalwan, Ashutosh | Muñoz, José J.Computer Methods in Applied Mechanics and Engineering, Vol. 420 (2024), Iss. P.116697
https://doi.org/10.1016/j.cma.2023.116697 [Citations: 1] -
Stabilized BB projection algorithm for large-scale convex constrained nonlinear monotone equations to signal and image processing problems
Rao, Jiayun | Yu, Chaozhi | Huang, NaJournal of Computational and Applied Mathematics, Vol. 448 (2024), Iss. P.115916
https://doi.org/10.1016/j.cam.2024.115916 [Citations: 0] -
Safeguarding adaptive methods: global convergence of Barzilai-Borwein and other stepsize choices
Ou, Hongjia | Themelis, Andreas2024 10th International Conference on Control, Decision and Information Technologies (CoDIT), (2024), P.2802
https://doi.org/10.1109/CoDIT62066.2024.10708282 [Citations: 0] -
A family of optimal weighted conjugate-gradient-type methods for strictly convex quadratic minimization
Oviedo, Harry | Andreani, Roberto | Raydan, MarcosNumerical Algorithms, Vol. 90 (2022), Iss. 3 P.1225
https://doi.org/10.1007/s11075-021-01228-0 [Citations: 3] -
Adaptive proximal algorithms for convex optimization under local Lipschitz continuity of the gradient
Latafat, Puya | Themelis, Andreas | Stella, Lorenzo | Patrinos, PanagiotisMathematical Programming, Vol. (2024), Iss.
https://doi.org/10.1007/s10107-024-02143-7 [Citations: 1] -
A Note on R-Linear Convergence of Nonmonotone Gradient Methods
Li, Xin-Rui | Huang, Ya-KuiJournal of the Operations Research Society of China, Vol. (2023), Iss.
https://doi.org/10.1007/s40305-023-00468-2 [Citations: 2] -
Fast methods for computing centroidal Laguerre tessellations for prescribed volume fractions with applications to microstructure generation of polycrystalline materials
Kuhn, Jannick | Schneider, Matti | Sonnweber-Ribic, Petra | Böhlke, ThomasComputer Methods in Applied Mechanics and Engineering, Vol. 369 (2020), Iss. P.113175
https://doi.org/10.1016/j.cma.2020.113175 [Citations: 21]