Inexact Barzilai-Borwein method for saddle point problems

doi:10.1002/nla.516

	Inexact Barzilai-Borwein method for saddle point problems
	Hu, Yi-Qing; Dai, Yu-Hong
	2007-05-01
发表期刊	NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS
ISSN	1070-5325
卷号	14 期号:4 页码:299-317
摘要	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 that g(k) and (g) over tilde (k) are the exact residual and its approximation of the linear system at the k th iteration, respectively. We prove the R-linear convergence of the algorithm if vertical bar vertical bar(g) over tilde (k) - g(k) vertical bar vertical bar <= eta vertical bar vertical bar (g) over tilde (k) vertical bar vertical bar for some small eta>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 vertical bar vertical bar (g) over tilde (k) vertical bar vertical bar is replaced by vertical bar vertical bar (g) over tilde (k-1) vertical bar vertical bar. Although our theoretical analyses cannot provide a good estimate to the parameter eta, in practice, we find that eta can he 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 (c) 2007 John Wiley & Sons, Ltd.
关键词	saddle point problem Uzawa algorithm Barzilai-Borwein method R-linear convergence
DOI	10.1002/nla.516
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied ; Mathematics
WOS记录号	WOS:000245958400004
出版者	JOHN WILEY & SONS LTD
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/5147
专题	计算数学与科学工程计算研究所
通讯作者	Dai, Yu-Hong
作者单位	Chinese Acad Sci, State Key Lab Sci & Engn Comp, Inst Computat Math & Sci Engn Comp, Acad Math & Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Hu, Yi-Qing,Dai, Yu-Hong. Inexact Barzilai-Borwein method for saddle point problems[J]. NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS,2007,14(4):299-317.
APA	Hu, Yi-Qing,&Dai, Yu-Hong.(2007).Inexact Barzilai-Borwein method for saddle point problems.NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS,14(4),299-317.
MLA	Hu, Yi-Qing,et al."Inexact Barzilai-Borwein method for saddle point problems".NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS 14.4(2007):299-317.