Volume 37, Issue 6
Stabilized Barzilai-Borwein Method

Oleg Burdakov, Yuhong Dai & Na Huang

J. Comp. Math., 37 (2019), pp. 916-936.

Published online: 2019-11

[An open-access article; the PDF is free to any online user.]

Preview Full PDF 197 4030
Export citation
  • 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 for the steepest descent (Cauchy) method, but its stepsize 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.

  • Keywords

Unconstrained optimization, Spectral algorithms, Stabilization, Convergence analysis.

  • AMS Subject Headings

65K05, 90C06, 90C30

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

oleg.burdakov@liu.se (Oleg Burdakov)

dyh@lsec.cc.ac.cn (Yuhong Dai)

hna@cau.edu.cn (Na Huang)

  • BibTex
  • RIS
  • TXT
@Article{JCM-37-916, author = {Burdakov , Oleg and Dai , Yuhong and Huang , Na }, title = {Stabilized Barzilai-Borwein Method}, journal = {Journal of Computational Mathematics}, year = {2019}, volume = {37}, number = {6}, pages = {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 for the steepest descent (Cauchy) method, but its stepsize 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.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1911-m2019-0171}, url = {http://global-sci.org/intro/article_detail/jcm/13383.html} }
TY - JOUR T1 - Stabilized Barzilai-Borwein Method AU - Burdakov , Oleg AU - Dai , Yuhong AU - Huang , Na JO - Journal of Computational Mathematics VL - 6 SP - 916 EP - 936 PY - 2019 DA - 2019/11 SN - 37 DO - http://dor.org/10.4208/jcm.1911-m2019-0171 UR - https://global-sci.org/intro/article_detail/jcm/13383.html KW - Unconstrained optimization, Spectral algorithms, Stabilization, Convergence analysis. AB -

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 for the steepest descent (Cauchy) method, but its stepsize 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.

Oleg Burdakov, Yuhong Dai & Na Huang. (2019). Stabilized Barzilai-Borwein Method. Journal of Computational Mathematics. 37 (6). 916-936. doi:10.4208/jcm.1911-m2019-0171
Copy to clipboard
The citation has been copied to your clipboard