资源描述：
《非单调线性互补问题内点算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、三峡大学硕士学位论文非单调线性互补问题内点算法的研究姓名：龚小玉申请学位级别：硕士专业：应用数学指导教师：张明望20070401AbstractIn1947,Danzigpresentedtheconceptionoflinearprogrammingandthefamoussimplexalgorithm.Althoughthesimplexmethodisefficientinsomepracticalapplications,itisnotthepolynomialtimealgorithm.In1978,thef
2、irstpolynomialalgorithmforlinearprogrammingproblem--theellipsoidalmethodwasproposedbyL.G.Khachiyan.Butunfortunately,thepracticalimplementationofthealgorithmhasbeenirremediablyinefficientthanthesimplexmethod.Somanyscholarstriedtodesignapolynomialalgorithmwithbette
3、rcalculationefficiencyforsolvinglinearprogramming.In1984,byuseofthepotentialfunctionandtheprojectiontransformation,Karmarkarproposedaalgorithmforlinearprogramming--interiorpointalgorithm.SincethepublicationofKarmarkar’spaper,interiorpointalgorithmhasbeenaveryacti
4、veresearchdirectioninmathematicalprogramminginrecent20years.Karmarkar’salgorithmnotonlyhasabetterpolynomialcomplexitythantheellipsoidmethod,butisalsoachallengingcompetitorofthesimplexmethodinpractice,especiallyforlargescaleproblems.Thisthesisisdevotedtostudyingth
5、ecomplementarityproblems,whichisanimportantbranchinmathematicalprogrammingandpossessesextensiveapplicationsinmanyfieldssuchaseconomyanalysisandtrafficequilibrium.Therefore,itissignificanttostudythealgorithmforsolvingthecomplementarityproblems.Thethesismainlydeals
6、withthestudyofinteriorpointalgorithmsforthenon-monotonelinearcomplementarityproblems,andanalyzesitsconvergenceindetail.Atlast,somenumericalexperimentsshowtheefficiencyofmethods.Thethesiscontainsfivechapters.Charpteroneintroducessomefundamentalknowledgeofthecomple
7、mentarityproblem,thendescribesthehistoricalbackgroundandthenpresentresearchconditionsofinteriorpointalgorithm.Thesecondandthirdchaptersarethecorepartsofthisthesis.Chaptertwodiscussestheinterior-pointalgorithmforsolvingthenon-monotonelinearcomplementarityproblemby
8、usingdifferentneighborhoods.Incharpterthree,basedonaspecificalgebraictransformationandtheframeofKMMalgorithm,anewinfeasibleinterioralgorithmforPlinearcomplemen
