Alternate step gradient method*

*This work was also reported on the International Workshop on “Optimization and Control with Applications”, Erice, Italy, July 9–17, 2001

Abstract

The Barzilai and Borwein (BB) gradient method does not guarantee a descent in the objective function at each iteration, but performs better than the classical steepest descent (SD) method in practice. So far, the BB method has found many successful applications and generalizations in linear systems, unconstrained optimization, convex-constrained optimization, stochastic optimization, etc. In this article, we propose a new gradient method that uses the SD and the BB steps alternately. Hence the name “alternate step (AS) gradient method.” Our theoretical and numerical analyses show that the AS method is a promising alternative to the BB method for linear systems. Unconstrained optimization algorithms related to the AS method are also discussed. Particularly, a more efficient gradient algorithm is provided by exploring the idea of the AS method in the GBB algorithm by Raydan (1997).

To establish a general R-linear convergence result for gradient methods, an important property of the stepsize is drawn in this article. Consequently, R-linear convergence result is established for a large collection of gradient methods, including the AS method. Some interesting insights into gradient methods and discussion about monotonicity and nonmonotonicity are also given.

Keywords:

• Linear system
• Unconstrained optimization
• Gradient method
• Convergence rate
• Nonmonotone line search
• Mathematics Subject Classifications 2000: 65K05
• 90C52

Acknowledgments

The author thanks Prof. Shao-lin Xi for providing the reference [16], Prof. Ya-xiang Yuan for his interesting discussions with the author about monotonicity and nonmonotonicity, and Dr. Da-chuan Xu for his careful reading of an early version of this article. Many thanks are also due to the referees, whose comments and suggestions improved this article greatly. This research was supported by the Chinese NSF grants 19801033 and 10171104 and a youth innovation fund of Chinese Academy of Sciences.

Notes

*This work was also reported on the International Workshop on “Optimization and Control with Applications”, Erice, Italy, July 9–17, 2001