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

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

1、AbstractInterior-pointalgorithm,asoneofthemostefficientalgorithms,notonlyhaspolynomialcomplexity,butalsohassuperiorpracticalperformance.Sincethefirstpracticalpolynomialinterior-pointalgorithmwaspresentedbyKarmarkarin1984,theresearchesonInterior-PointMethods(IPMs)hasachievedfruitfulresult.Atpresent

2、,interior-pointalgorithmsaresuccessfullyusedforsolvingLinearProgramming,ConvexProgramming,ComplementarityProblems,Semi-definiteProgrammingandSecond・orderConeOptimization.SeveralpowerfulIPMsbasedoptimizationpackageshavebeendevelopedandwidelyused.ThisthesisisdevotedtostudyingMehrotra-typepredictor-c

3、orrectoralgorithmsfor£(k)complementarityproblems.Complementarityproblemisaclassofthewidelyusedmathematicalproblems,whichhasimportantapplicationsinengineering,economicanalysisandtrafficequilibrium.Therefore,itissignificanttostudythealgorithmsforsolvingthe£(k)complementarityproblems.Thethesismajorsi

4、nresearchingonMehrotra-typepredictor-correctoralgorithmsforE(k)linearcomplementarityproblemand尺(k)nonlinearcomplementarityproblems.Threenewalgorithmsarepresentedandthepolynomialcomplexityofthemisproved.Thethesiscontainsfourchapters.Chapteroneintroducessomepreliminaryknowledgeandresearchbackgrounds

5、.ChaptertwopresentsaMehrotra-typepredictorcorrectoralgorithmforR(k)linearcomplementarityproblem,thepolynomialcomplexityofwhichisgiven.Anumericalexperimentverifiestheefficiencyofthealgorithm.InChapterthree,twoMehrotra-typepredictor-correctoralgorithmsbasedon"safetystrategy^aregiven,oneforsolvingmo

6、notonenonlinearcomplementarityproblemandanotherfor/i(k)nonlinearcomplementarityproblem.WiththeassumptionoftheScaledLipschitzCondition,weprovedthepolynomialcomplexityofthealgorithms.Finally,aconclusionismaderegardingthediscusstopictogetherwiththefurtherexpectationinChapterfour.Keywords:interior-poi

7、ntalgorithmcomplementarityproblemMehrotra-typepredictor-correctoralgorithmpolynomialcomplexity目录弓丨言11绪论21.1互补问题简介21.2内点算法的产生与发展概况21.3基本概念及符号约定42R(k)线性互补问题的Mehrotra型预估-校正算法62.1£(k)线性互补问题介绍62.2算法描述72.3算法复杂性分析92.4数值