A new gradient method with an optimal stepsize property

Y. H. Dai, Xiaoqi Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

15 Citations (Scopus)

Abstract

The gradient method for the symmetric positive definite linear system Ax=b is as follows xk + 1=xk- αkgkwhere gk=Axk-b is the residual of the system at xkand αkis the stepsize. The stepsize alphak= 2/λ1+λnis optimal in the sense that it minimizes the modulus ||I - α A||2, where λ1and λnare the minimal and maximal eigenvalues of A respectively. Since λ1and λnare unknown to users, it is usual that the gradient method with the optimal stepsize is only mentioned in theory. In this paper, we will propose a new stepsize formula which tends to the optimal stepsize as k → ∞. At the same time, the minimal and maximal eigenvalues, λ1and λn, of A and their corresponding eigenvectors can be obtained.
Original languageEnglish
Pages (from-to)73-88
Number of pages16
JournalComputational Optimization and Applications
Volume33
Issue number1
DOIs
Publication statusPublished - 1 Jan 2006

Keywords

  • (Shifted) power method
  • Gradient method
  • Linear system
  • Steepest descent method

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Applied Mathematics

Cite this