pk线性互补问题的mehrotra型预估校正算法研究及拓展

《pk线性互补问题的mehrotra型预估校正算法研究及拓展》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、``ADissertationSubmittedinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofScienceTheResearchesonMehrotra-TypePredictor-CorrectorAlgorithmforP*(k)ComplementarityProblemsandItsExtension`````````GraduateStudent:Major:Supervisor:LiWeihuaAppliedMathematics

2、Prof.ZhangMingwang`````````ChinaThreeGorgesUniversityYichang,443002,P.R.ChinaMay,2011`````````三峡大学硕士学位论文`````````三峡大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果，除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明，本人完全意识到本声明的

3、法律后果由本人承担。学位论文作者签名：`````````I日`````````期：`````````三峡大学硕士学位论文`````````内容摘要内点算法作为求解优化问题的有效算法之一，不仅具有多项式收敛性，还有良好的实际计算效果.自1984年第一个具有实用性的多项式内点算法——Karmarkar算法提出以来，经过二十多年的发展，内点算法的研究已取得了丰硕的成果.如今，内点算法已被成功地应用于求解线性规划、凸规划、互补问题、半定规划、二阶锥规划等众多优化问题.许多基于内点算法的优化软件包被开发并

4、被广泛利用.本文主要研究P*(k)互补问题的Mehrotra型预估-校正算法.互补问题是一类应用广泛的数学问题，被应用于工程、经济分析、交通平衡及最优控制等众多领域.因此，对互补问题的研究有重要的理论价值和实际意义.本文的研究工作主要是对线性规划的Mehrotra型预估-校正算法的推广，将其应用于求解P*(k)线性互补问题和P*(k)非线性互补问题，并探讨新算法的多项式迭代复杂性.全文分为四章.第一章简要介绍相关基础知识及研究背景；第二章提出了一种P*(k)线性互补问题的Mehrotra型预估-校正算法，并给出了算法

5、的多项式复杂性证明，还通过数值实验验证了算法的有效性；第三章针对单调非线性互补问题和P*(k)非线性互补问题，分别设计了基于“安全步策略”的Mehrotra型预估-校正算法，并在映射满足尺度化李普希茨条件(ScaledLipschitzCondition)的假设下，证明了这两种算法的多项式迭代复杂性；第四章总结全文，并对后续工作进行了展望.`````````关键词：内点算法互补问题Mehrotra型预估-校正算法多项式复杂性``````````````````II`````````三峡大学硕士学位

6、论文`````````AbstractInterior-pointalgorithm,asoneofthemostefficientalgorithms,notonlyhaspolynomialcomplexity,butalsohassuperiorpracticalperformance.Sincethefirstpracticalpolynomialinterior-pointalgorithmwaspresentedbyKarmarkarin1984,theresearchesonInterior-Poi

7、ntMethods(IPMs)hasachievedfruitfulresult.Atpresent,interior-pointalgorithmsaresuccessfullyusedforsolvingLinearProgramming,ConvexProgramming,ComplementarityProblems,Semi-definiteProgrammingandSecond-orderConeOptimization.SeveralpowerfulIPMsbasedoptimizationpacka

8、geshavebeendevelopedandwidelyused.ThisthesisisdevotedtostudyingMehrotra-typepredictor-correctoralgorithmsforP*(k)complementarityproblems.Complementarityproblemisaclassofthew