可行域收縮內(nèi)點(diǎn)算法.pdf

1、東南大學(xué)碩士學(xué)位論文可行域收縮內(nèi)點(diǎn)算法姓名：李琛申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：潘平奇20040312AbstractTheresearchintheinteriorpointmethodsforlinearprogrammingwasspurredbythepubli—cationofKarmarkaralgorithmin1984，Sincethen＆greatnumberofalgorithmsbasedonith

2、avebeendeveloped，inwhichAffinescalingmethodsareoutstandingIttransformsthelinearprogramstandardformtoanequivanlentoneinwhichthecurrentpointisfavorablyforaconstrainedformofthesteepest—descentmethodAffinescalingmethodsareth

3、esimplestofinteriorpointmeth—ods，yettheyareeffectiveatsolvinglargeproblemsWhilePath—followingmethods，whichattempttostayclosetothebarriertrajectoryareanothereffectiveinteriorpointmethodsAlthoughbarriermethodsfornonlinearp

4、rogrammingwereproposedinthe1950sItwasonlywiththepublicationofKarmarkar’SalgorithmthatinterestinthisapproachwasrekindledInfactKarmarkar’SmethodmaybeviewedasaspecialcaseofabarriermethodWetrytofindapotential—reductionmethod

5、forlinearprogrambycombiningthethoughtofaffinescalingandcentraltrajectoryForstandardlinearprogram，wedefineanauxiliaryproblemofbarrierfunctiontomakepotentialreductionatthecurrentinteriorpointThenwemaygetitssteepest—descent

6、directionbyaffinescalingtransformationIngeometrytheabovemethodmeaTisthatweaddafacewhichisparalleltotheequivalent—valuefaceoftheobjectfunction，tothefeasibleregionateachiterationSowegetaretractedfeasibleregionandthecurrent

7、pointisstillininterioroftheretractedfeasibleregionThenwegetthenextinteriorpointinfeasiblesteepestdescentdirectionandthevalueofobjectfunctionreducesInsuchway，thefaceretractstowardtheoptimalpointandthealgorithmterminatewhe

8、nitsatisfiesthedefinedprecisionWemakethenumbericalexperimentfortheabovethreealgorithmsandourprdiminarycomputationalexperimentsshowthatFeasibleregionretractionmethodoutperformedprimalpathfollowingmethodandprimalamnescalin