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