預(yù)估—校正算法在線性和半定規(guī)劃中的討論.pdf

1、同濟(jì)大學(xué)理學(xué)院碩士學(xué)位論文預(yù)估—校正算法在線性和半定規(guī)劃中的討論姓名：朱曉梅申請學(xué)位級別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：濮定國20060301AbstractThispapermainlystudiestwodifferentkindsofinteriorpointpredictorcorrectoralgorithmsforlinearprogrammingandsemidefiniteprogrammingThesocalled

2、predictorcorrectoralgorithmmeanstakingacorrectorstepafterthepredictorstepMostpathfollowingalgorithmsonlyi150predictorsteps，anddonottakecorrectorstepsInordertoensuretheworstcasecomplexitywemostfixthecentringparameterthent

3、hiswilllimitthepossibleconvergencespeedWh協(xié)weallowlargeimprovementandletcentringparametercqualto0，tofindreasonablestep，wemustenlargetheneighborhoodofthecentralpathinthepredictorstepthenthecorre∞torstepisnecessaryThesetwoa

4、lgorithmsonlyfixtheiteratesinthckBarrOWneighborhoodsand啪onlybeusedforeitherlinearprogrammingorsemidefiniteprogrammingSotosomeextenttheyarelimitedandrestricttheapplicationinchoosinginitialpointsThispaperistoimprovethemeth

5、ods，eliminatetheselimitationsandextendthealgorithms，sothattheyCallbeusedforbothlinearprogrammingandsemidefiniteprogramming’Themainjobsofthispaperareasfollows：1Analyzingthetheoreticbasisoftheinteriorpointforlinearprogramm

6、ingandsemidefiniteprogrammingandprovidingthecorrespondingtheoreticfoundationforpredictorcorrectoralgorithms2Extendingtherangeoftheparametersandgivingproofsfortheformerpredictorcorrectoralgorithmusedforsemidefiniteprogram

7、mingandthenspecializingtheimprovedalgorithmtolinearprogramming3MakingtheparametersgeneticfirstfortheformerPredictorCorrectoralgorithmusedforlinearprogrammingthenintroducingoperatorstochangetheformofthesystem，givingproofs