凸二次规划的一个改进的Mehrotra型预估-校正算法.pdf

2011年 9月 高 等 学 校 计 算 数 学 学 报 第 33卷第 3期 凸二次规划的一个改进的Mehrotr 预估一校正算法木 赵玉琴 张明望 周意元 (三峡大学理学院，宜昌443002) 0N M EHRoTRA—TYPE PRED ICToR．C0RRECToR ALGORITHM FOR CoNVEX QUADRATIC PRoGRAM M ING ZhaoYuqin ZhangM ingwang ZhouYiyuan (ScienceCollege，ChinaThreeGorgesUniversity,Yichang443002) Abstract Mehrotra．．typepredictor．．correctoralgorithmsarethebackboneofthe mostinteriorpointmethodsbased OIlthesoftwarepackages，RecentlySalahiet a1．consideravariantofMehrotra’Scelebratedpredictor—correctoralgorithm for linearoptimizationproblem．Byanumericalexampletheyshow thatthisvariant mightmakeverysmallstepsin ordertokeeptheiterateinacertain neightbor— hoodofthecentralpaththatitselfimpliestheine币ciencyofthealgorithm ．This observationmotivatthem toincorporatesafeguardintheiralgorithm schemethat givesalowerboundforthestepsizeateachiterationandthusimpliespolynomial iteration complexity．Thispaperextendstheirmodified approachtotheconvex quadraticprogramm ing．Asthesearchdirections△z and Asarenotorthogonal any more．thecomplexityanalysisofthemethod isdifierentfrom thatoflinear programm ing，correspondiIlgly．Welprovethattheextendedalgorithm ，intheworst casewillterminateafteratmostO(nlog 专 )iterations． Key words convex quadratic programming， predictor—corrector method， methrotra-typealgorithm ，polynom ialcomplexity． AMS(2000)subjectclassi矗cations 90C33 中图法分类号 O221 湖北省自然科学基金项目(2008CDZ047)，三峡大学青年科学基金项目(KJ2009A028) 收稿 日期：2008—08—08． 2011年 9月 高 等 学 校 计 算 数 学 学 报 251． 1 引 言 自1984年 Karmarkar提出 [1】以来，内点算法成为最活跃的研究领域之一，至今取 得了大量的成果。此外，人们开发了许多基于内点算法的优化软件包。预估 一校正算法是 最有效的内点算法之一，并且成为众多优化软件的核心算法。大部分数值实现都是基于 文献 2【】中Mehrotra的预估一校正算