Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming

doi:10.1007/s00211-004-0569-y

	Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming
	Dai, YH; Fletcher, R
	2005-03-01
发表期刊	NUMERISCHE MATHEMATIK
ISSN	0029-599X
卷号	100 期号:1 页码:21-47
摘要	This paper studies projected Barzilai-Borwein (PBB) methods for large-scale box-constrained quadratic programming. Recent work on this method has modified the PBB method by incorporating the Grippo-Lampariello-Lucidi (GLL) nonmonotone line search, so as to enable global convergence to be proved. We show by many numerical experiments that the performance of the PBB method deteriorates if the GLL line search is used. We have therefore considered the question of whether the unmodified method is globally convergent, which we show not to be the case, by exhibiting a counter example in which the method cycles. A new projected gradient method (PABB) is then considered that alternately uses the two Barzilai-Borwein steplengths. We also give an example in which this method may cycle, although its practical performance is seen to be superior to the PBB method. With the aim of both ensuring global convergence and preserving the good numerical performance of the unmodified methods, we examine other recent work on nonmonotone line searches, and propose a new adaptive variant with some attractive features. Further numerical experiments show that the PABB method with the adaptive line search is the best BB-like method in the positive definite case, and it compares reasonably well against the GPCG algorithm of More and Toraldo. In the indefinite case, the PBB method with the adaptive line search is shown on some examples to find local minima with better solution values, and hence may be preferred for this reason.
DOI	10.1007/s00211-004-0569-y
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000227511900002
出版者	SPRINGER
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/1915
专题	计算数学与科学工程计算研究所
通讯作者	Dai, YH
作者单位	1.Chinese Acad Sci, State Key Lab Sci & Engn Comp, Inst Comuptat Math & Sci Engn Comp, Acad Math & Syst Sci, Beijing 100080, Peoples R China 2.Univ Dundee, Dept Math, Dundee DD1 4HN, Scotland
推荐引用方式 GB/T 7714	Dai, YH,Fletcher, R. Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming[J]. NUMERISCHE MATHEMATIK,2005,100(1):21-47.
APA	Dai, YH,&Fletcher, R.(2005).Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming.NUMERISCHE MATHEMATIK,100(1),21-47.
MLA	Dai, YH,et al."Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming".NUMERISCHE MATHEMATIK 100.1(2005):21-47.