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