Inexact Barzilai‐Borwein method for saddle point problems
Yi‐Qing Hu, Yu‐Hong Dai · Numerical Linear Algebra with Applications · 2007
Abstract This paper considers the inexact Barzilai–Borwein (BB) algorithm applied to saddle point problems. To this aim, we study the convergence properties of the inexact BB algorithm for symmetric positive definite linear systems. Suppose thatgkandg̃kare the exact residual and its approximation of the linear system at thekth iteration, respectively. We prove theR‐linear convergence of the algorithm if ∥g̃k–gk∥⩽η∥g̃k∥ for some small η>0 and allk. To adapt the algorithm for solving saddle point problems, we also extend theR‐linear convergence result to the case when the right‐hand term ∥g̃k∥ is replaced by ∥g̃k–1∥. Although our theoretical analyses cannot provide a good estimate to the parameter η, in practice, we find that η can be as large as the one in the inexact Uzawa algorithm. Further numerical experiments show that the inexact BB algorithm performs well for the tested saddle point problems. Copyright © 2007 John Wiley & Sons, Ltd.