拓展熵規(guī)劃內(nèi)點(diǎn)算法的復(fù)雜性研究.pdf

1、上海大學(xué)碩士學(xué)位論文拓展熵規(guī)劃內(nèi)點(diǎn)算法的復(fù)雜性研究姓名：龐莉莉申請(qǐng)學(xué)位級(jí)別：碩士專業(yè)：運(yùn)籌學(xué)與控制論指導(dǎo)教師：田蔚文20060501AbstractIVIngeneral，itneedstofindtheinitialfeasiblepointwhenwesolvetheconvexprogrmluulngusinginteriorpointmethod，yetitisverydifficulttofindtheinitialfeasi

2、blepointSometimesthecomple。xitytofindtheinitialfeasiblepointissameasthatwesolvetheorigihalproblemInljghtoftheselfdualembeddingmodelforlinearprogrammingandconicprogramming，thisthesisproposetosolvetheextendedentropyprogram

3、mingproblemusingconicsdfduMembeddingulodelWetransformtheextendedentropypr091rmnmingproblemintoconicprogramming，thenconstructaconicselfdualembeddingmodelforthetransformedconicprogrammingTheembeddingmodelisguaranteedtohave

4、anoptimalsolutionwecansolvetheinfeasibleorunboundedproblemsusingtheembeddingmodelThismethoddoesnotneedtofindtheinitialfeasiblesolutionAndweprovethatthebarrierfunctionisself_eoneordant，thisguaranteesthealgorithmispolynonf

5、ialalgorithmwhenusesomeinteriorpointmethodtosolvethisproblemInChapter1，abriefintroductionisgiventothedevelopmentofinteriorpointmethodandtheextendedentropyprogrammingInChapter2，weintroducesomeinteriorpointmethodsInChapter

6、3，wefocusonthetheoryofselfconcordaaey，andtherelationbetweenthecomplexityofconvexprogrammingandselfconcordanc礦InChapter4，weintroducetheconicoptimizationandconicselfdualembeddingmodelInChapter5，westudytheextendedentropypro