\(R\)-linear convergence of the Barzilai and Borwein gradient method. (English) Zbl 1002.65069

Authors’ abstract: Combined with non-monotone line search, the two-point step size gradient method of J. Barzilai and J. M. Borwein [(BB) ibid. 8, No. 1, 141-148 (1988; Zbl 0638.65055)] has been successfully extended for solving unconstrained optimization problems and is competitive with conjugate gradient methods. In this paper, we establish the \(R\)-linear convergence of the BB method for any-dimensional strongly convex quadratics. One corollary of this result is that the BB method is also locally \(R\)-linear convergent for general objective functions, and hence the stepsize in the BB method will always be accepted by the non-monotone line search when the iterate is close to the solution.


65K05 Numerical mathematical programming methods
90C25 Convex programming


Zbl 0638.65055
Full Text: DOI