線性互補(bǔ)問題基于核函數(shù)的內(nèi)點(diǎn)算法.pdf

1、上海大學(xué)碩士學(xué)位論文線性互補(bǔ)問題基于核函數(shù)的內(nèi)點(diǎn)算法姓名：劉勇申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：白延琴20080401ABSTRACTThecomplementarityproblem(CP)isoneoftheimportantoptimizationproblemsItbelongstothefieldsofoperationsresearchandcomputationalmathematicsIthasaclose

2、relationwithlinearprogramming(LP)，nonlinearprogramming，minimaxtheorymetagametheorythetheoryoffixedpointandotherfiliationsofoptimizationtheoryItappearsintheoptimialconditionsofconstrainedoptimizationInpractice，ithaswideap

3、plicationsinengineering，economics，operationsresearch，managementscienceandotherfieldsThestudyforthecomplementarityproblemisfunofthemeaningtheoreticallyandpracticallyRoughlyspeaking，theresearchOiltheCPcanbeclassifiedintotw

4、oclasses：theoryandalgorithmsTheformerisdevotedtotheexistence，uniqueness，stabilityandsensitivityanalysisofthesolutionswhilethelatterisintendedtosolvetheproblemsefficientlytogetherwiththetheoreticalanalysisofthealgorithmsI

5、nthisthesis，weconsiderthemonotonelinearcomplementarityproblem(MLCP)，whichisoneoftheimportantCPsWediscussgeneralexpressionofthekernelfunctionsandgeneralizetheirpropertiesAndthen，wepresentapathfoHowinginteriorpointalgorith

6、mbasedonthegeneralkernelfunctionsforMLCPsFurthermoreweanalyzethecomplexityofthealgorithmandobrainaconsistentiterationboundMoreover，weoutlineamethodwhichcanbeusedtocomputethetheoreticaliterationboundofthealgorithmbasedond

7、ifferentkernelfunctionsLikewiseweextendtheexpressionofkernelfunctionstoamoregeneralformanddiscusstheirpropertiesFinallyweusesomenumericalresultstoshowthattheiterationsofthealgorithmdependonthekernelfunctionsThisthesisinc

8、ludesfivechaptersInChapter1，weoverviewbrieflytheCPandthepirmaldualinterior—pointalgorithmsforLPInChapter2，weintroducethedefinitionofkernelfunctions，andgiveabriefconclusionofthekernelfunctionswhichexistedThegeneralkernelf

9、unctionsandtheirpropertiesarepresentedinthisChapterInChapter3，werecallthebasictheoreticsofMLCPsThenwepresentapathfollowinginteriorpointalgorithmbasedongeneralkernelfunctionsforMLCPs，analysisthecomplexityofthealgorithm，an

10、dobtainaconsistentiterationboundofthealgorithmWeoutlineamethodwhichcanbeusedtocomputethetheoreticaliterationboundofthealgorithmbasedondifferentkernelfunctionsWeextendtheexpressionofkernelfunctions’toamoregeneralformanddi