資源描述：
《應(yīng)用改進(jìn)的內(nèi)點(diǎn)法求二階錐規(guī)劃的最優(yōu)解》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、應(yīng)用改進(jìn)的內(nèi)點(diǎn)法求二階錐規(guī)劃的最優(yōu)解王璐1,高雷阜1（1遼寧工程技術(shù)大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)研究所,遼寧阜新123000)摘要：本文針對(duì)二階錐規(guī)劃的優(yōu)化問(wèn)題提出了一種改進(jìn)的非精確內(nèi)點(diǎn)算法。本算法允許搜索方向有相對(duì)較大的誤差，且不要求迭代點(diǎn)的可行性，在相對(duì)不精確的假設(shè)下，利用該算法可找到二階錐規(guī)劃的近似解。從實(shí)驗(yàn)的結(jié)果可以看出,改進(jìn)算法的性能得到了顯著的提高。關(guān)鍵詞：二階錐規(guī)劃；非精確搜索方向；內(nèi)點(diǎn)算法中圖分類號(hào)：O232文獻(xiàn)標(biāo)識(shí)碼：AAnApplicationofImprovedinteriorpointalgorithmonsecond-orderco
2、neprogrammingWangLu1,GaoLei–fu1(1.MathematicsandSystemsScienceInstituteofLiaoningTechnologyUniversityLiaoningFuxin123000)Abstract:Ainexactinteriorpointalgorithmispresentedforsolvingthesecond-orderconeprogramming(SOCP)problem.Thesearchdirectionofthisalgorithmallowsarelativelyla
3、rgererroranddosenotrequireinterationpointstobewithinthesetsofstrictlyfeasiblesolutions,undermildassumptionsontheinexactness,wecanfindanapproximatesolutionoftheSOCPbyusingthisalgorithm.Numericalresultssuggesttheeffectivenessofourproposedalgorithm.Keywords:second-orderconeprogra
4、mming;inexactsearchdirection;interiorpointalgorithm0引言二階錐規(guī)劃問(wèn)題是一族凸優(yōu)化問(wèn)題，而非線性規(guī)劃，它是半定規(guī)劃的特例。人們對(duì)二階錐規(guī)劃的研究已經(jīng)有很長(zhǎng)的歷史了，如經(jīng)典的Fermat-Weber問(wèn)題可追溯到幾個(gè)世紀(jì)以前,由于把二階錐規(guī)劃轉(zhuǎn)化成半定規(guī)劃求解，其效果并不很理想，因此人們開始對(duì)二階錐規(guī)劃進(jìn)行深入研究。對(duì)二階錐規(guī)劃的研究主要是建立在歐幾里得約當(dāng)代數(shù)基礎(chǔ)上的，F(xiàn)aruat和Konary詳細(xì)論述了這一理論。隨后Nesetorv和Nemiorvski提出了用內(nèi)點(diǎn)法求解凸規(guī)劃的理論。上世紀(jì)九十年
5、代，人們開始用內(nèi)點(diǎn)法求解二階錐規(guī)劃及其特例(凸二約束下的二次規(guī)劃)，自Nesteorv和Todd第一次用多項(xiàng)式時(shí)間原-對(duì)偶路徑跟蹤法以來(lái)，求解二階錐規(guī)劃的原-對(duì)偶內(nèi)點(diǎn)算法才得以長(zhǎng)足發(fā)展。目前，對(duì)于二階錐規(guī)劃算法與性質(zhì)的研究以及其在各領(lǐng)域的廣泛應(yīng)用都有了較大的進(jìn)展，本文將對(duì)二階錐規(guī)劃的內(nèi)點(diǎn)算法做進(jìn)一步的研究。基于文獻(xiàn)[3]中半定規(guī)劃的算法，提出了一種新的改進(jìn)的非精確內(nèi)點(diǎn)算法。1相關(guān)概念定義1二階錐及其規(guī)劃二階錐定義為：，為二階錐的維數(shù).其原規(guī)劃為：對(duì)偶規(guī)劃為：，其中。定義2歐幾里得約當(dāng)代數(shù)二階錐規(guī)劃的算法是基于約當(dāng)代數(shù)發(fā)展起來(lái)的，與二階錐相伴的歐幾里
6、得約當(dāng)代數(shù)定義為：，其中。令，則有，其中定義3向量的譜分解,從而被寫成，其中，，，將分成塊處理,其中,則，,,,定義4約當(dāng)塊的標(biāo)準(zhǔn)化定義標(biāo)準(zhǔn)約當(dāng)塊,其中標(biāo)準(zhǔn)特征向量，將約當(dāng)塊轉(zhuǎn)化為約當(dāng)塊，通過(guò)下面式子：，詳見文獻(xiàn)[4]。因此,2非精確內(nèi)點(diǎn)算法2.1主要思想內(nèi)點(diǎn)算法是一類求解二階錐規(guī)劃的非常有效的方法,在內(nèi)點(diǎn)算法的每一步迭代中主要工作是通過(guò)求解一個(gè)非線性方程組來(lái)找一個(gè)搜索方向，但是由于計(jì)算機(jī)的精度原因，由以前的方法直接求解不僅花費(fèi)了大量計(jì)算時(shí)間，而且得不到真正精確的搜索方向.事實(shí)上，非精確內(nèi)點(diǎn)算法的基本思想是在中心路徑的鄰域內(nèi)圍繞中心路經(jīng)前進(jìn)，最終趨
7、向最優(yōu)點(diǎn)，但在計(jì)算過(guò)程中約當(dāng)矩陣會(huì)出現(xiàn)奇異的現(xiàn)象,導(dǎo)致算法不穩(wěn)定。本文提出的算法是將約當(dāng)塊通過(guò)函數(shù)進(jìn)行標(biāo)準(zhǔn)化處理，再利用非精確內(nèi)點(diǎn)算法求解二階錐規(guī)劃的最優(yōu)解，這樣既可保證算法的穩(wěn)定性，又可以保證算法的全局收斂性，節(jié)約了大量的計(jì)算時(shí)間，使算法變得更為有效.互補(bǔ)松弛定理：如果是二階錐原規(guī)劃的最優(yōu)解，是其對(duì)偶規(guī)劃的最優(yōu)解，那么?；诨パa(bǔ)松弛定理，譜分解定義及約當(dāng)塊的標(biāo)準(zhǔn)化的相關(guān)理論,二階錐規(guī)劃可轉(zhuǎn)化為:2.2中心路徑及其鄰域探索步：，，，牛頓線性方程組：2.3非精確內(nèi)點(diǎn)算法的實(shí)現(xiàn)假設(shè)：（1）是二階錐規(guī)劃的原-對(duì)偶可行解，是特征值。（2），其中選擇，初始點(diǎn)
8、，選擇，這樣使得。步1：選擇步2：計(jì)算牛頓線性方程組，從而解出搜索方向。步3：選擇探索步：，，，步4：。若或者，則停止。如
