Inexact Barzilai-Borwein Method for Saddle Point Problems ∗

This paper considers the inexact Barzilai-Borwein algorithm ap-plied to saddle point problems. To this aim, we study the convergence properties of the inexact Barzilai-Borwein algorithm for symmetric positive definite linear systems. Suppose that gk and g̃k are the exact residual and its approximation of the linear system at the k-th itera-tion, respectively. We prove the R-linear convergence of the algorithm if ‖g̃k − gk ‖ ≤ η‖g̃k ‖ for some small η> 0 and all k. To adapt the algorithm for solving saddle point problems, we also extend the R-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 nu-merical experiments show that the inexact Barzilai-Borwein algorithm performs well for the tested saddle point problems