本文關鍵詞：半定規(guī)劃的不可行內點算法

  更多相關文章： 半定規(guī)劃 不可行內點法 迭代復雜度 單調互補問題 全牛頓步

【摘要】：半定規(guī)劃(SDP)是線性規(guī)劃(LP)的進一步推廣,它的約束條件是非光滑的、凸的,因此,SDP是一個非光滑凸優(yōu)化問題。近年來,SDP在算法和理論上日漸發(fā)展,并廣泛的應用于組合優(yōu)化、圖像處理、模式識別等相關領域,成為數學規(guī)劃中一個非常重要的研究方向。在解決數學規(guī)劃問題的若干方法中,內點法(IPM)具有較好的實驗效果和較低的理論復雜度,成為半定規(guī)劃的核心算法。SDP內點法按其約束條件是否可行分成可行內點法(FIPM)和不可行內點法(IIPM),本文主要研究的是IIPM。一般內點法中理論復雜度小的算法實驗效果差,而實驗效果好的算法理論復雜度很高[1],而實際中往往希望在保持較好的實驗效果的同時降低算法的理論復雜度。為此,本文提出了兩種新的算法,分析了它們的多項式復雜度,并且做了數值實驗進行比較。主要完成了以下工作:1.首先概括了SDP的發(fā)展背景,然后簡要總結了SDP的基本概念和理論以及求解SDP問題的常用算法,介紹了SDP的研究現狀。2.齊次不可行內點法:為了降低SDP模型的迭代復雜度,并且有更好的數值實驗效果,本論文研究了一種新的寬鄰域上的齊次不可行內點法。SDP問題的KKT條件可以看作一個單調互補問題(MCP),通過構造齊次模型(HMCP)以及提出新的寬鄰域來解這個單調互補問題,從而提出了一種新算法,這種算法容易判定原來的SDP模型是否可行。當取NT方向時,證明了迭代點在新的寬鄰域內是收斂的,且迭代復雜度降低到(?)((?)logL),其中n是SDP問題的維數,L=Tr(X~0 S~0)/ε,ε是需要的精度,(X~0,S~0)是迭代起始點,這比一般的SDP不可行內點法的迭代復雜度低,同時做出了數值實驗列表,證明了此方法比其他不可行內點法具有更好的數值實驗效果。3.一種新的全牛頓步不可行內點法:全牛頓步算法分為可行步和中心步兩種全牛頓步,最大的優(yōu)勢就是不用求解步長,使算法的計算量降低。新算法引入了一個特別的核函數,用此核函數來代替可行步中的原始對數障礙函數,得到一種不同于一般算法的可行步,同時給出了一個更大的鄰域,在新鄰域中對二次收斂性結果的證明進行了改進,并且迭代復雜度和當前全牛頓步不可行內點法最好的迭代復雜度結果一致。
【關鍵詞】：半定規(guī)劃 不可行內點法 迭代復雜度 單調互補問題 全牛頓步
【學位授予單位】：西安電子科技大學
【學位級別】：碩士
【學位授予年份】：2015
【分類號】：O221
【目錄】：

• 摘要5-6
• ABSTRACT6-9
• 符號對照表9-10
• 縮略語對照10-13
• 第一章 緒論13-25
• 1.1 半定規(guī)劃的研究背景與進展13-14
• 1.2 半定規(guī)劃的基本理論14-17
• 1.2.1 半定規(guī)劃的基本概念14-16
• 1.2.2 半定規(guī)劃的對偶理論16-17
• 1.3 半定規(guī)劃的主要算法17-22
• 1.3.1 內點法18-21
• 1.3.2 非內點法21-22
• 1.4 半定規(guī)劃的研究現狀22-24
• 1.5 本文的主要工作和內容安排24-25
• 第二章 半定規(guī)劃的齊次不可行內點法25-43
• 2.1 引言25-27
• 2.2 齊次MCP模型HMCP27-29
• 2.3 齊次模型的中心路徑29-30
• 2.4 具有(?)((?)log L) 復雜性的齊次不可行內點法30-39
• 2.4.1 計算搜索方向30-34
• 2.4.2 不可行性和對偶間隙的下降關系34-36
• 2.4.3 齊次不可行內點法36
• 2.4.4 算法的復雜性分析36-39
• 2.5 數值實驗39-40
• 2.6 本章小結40-43
• 第三章 半定規(guī)劃的全牛頓步不可行內點法43-51
• 3.1 引言43-44
• 3.2 基于核函數的全牛頓步不可行內點法44-47
• 3.3 算法的復雜性分析47-50
• 3.4 本章小結50-51
• 結束語51-53
• 參考文獻53-59
• 致謝59-61
• 作者簡介61-62

【相似文獻】

中國期刊全文數據庫 前10條

1 房亮;;一類模糊半定規(guī)劃問題的解法[J];山東科技大學學報(自然科學版);2007年01期

2 徐引玲;;半定規(guī)劃問題的光滑化方法[J];西北師范大學學報(自然科學版);2008年02期

3 李明山;張明;李興瑋;董國華;;基于半定規(guī)劃的量子狀態(tài)最優(yōu)無錯區(qū)分[J];計算機仿真;2008年10期

4 馬宗剛;成央金;鄧勝岳;張美芳;;求解無線傳感器網絡定位的半定規(guī)劃松馳法[J];太原科技大學學報;2009年01期

5 田苗;劉紅衛(wèi);葉峰;;求解半定規(guī)劃問題的一種光滑化方法[J];西北大學學報(自然科學版);2009年01期

6 李蕊;;半定規(guī)劃的改進的外梯度法[J];重慶文理學院學報(自然科學版);2010年05期

7 李成進;;解特殊凸二次半定規(guī)劃的正則法[J];武夷學院學報;2010年05期

8 蘇麗娜;;圓形幾何布局優(yōu)化問題的非線性半定規(guī)劃解法[J];陰山學刊(自然科學);2011年04期

9 韓喬明;解半定規(guī)劃的Levenberg-Marquardt方法[J];數值計算與計算機應用;1998年02期

10 關秀翠,刁在筠;半定規(guī)劃的逆問題[J];經濟數學;1999年03期

中國重要會議論文全文數據庫 前7條

1 房亮;馮增哲;賀國平;李樹全;;非線性半定規(guī)劃問題的一種基于松弛變量的內點法[A];第八屆中國青年運籌信息管理學者大會論文集[C];2006年

2 王建宏;林道榮;;具線性矩陣不等式約束半定規(guī)劃問題的一種原始-對偶中心路徑算法[A];第九屆中國青年信息與管理學者大會論文集[C];2007年

3 崔艷;;二次{-1,1}規(guī)劃的半定規(guī)劃松弛的非線性規(guī)劃算法[A];第十二屆中國青年信息與管理學者大會論文集[C];2010年

4 王曉敏;劉靈;;半定規(guī)劃的原始-對偶不可行內點算法[A];2006年中國運籌學會數學規(guī)劃分會代表會議暨第六屆學術會議論文集[C];2006年

5 袁彥;白曉清;韋化;;求解變壓器新模型OPF的半定規(guī)劃法[A];中國高等學校電力系統(tǒng)及其自動化專業(yè)第二十四屆學術年會論文集（下冊）[C];2008年

6 王建宏;王曉敏;孔鵬志;王文慶;;半定規(guī)劃問題中的幾個擇一性定理[A];中國企業(yè)運籌學學術交流大會論文集[C];2007年

7 田媛;田志遠;;解半定規(guī)劃問題的Log-Sigmoid乘子法[A];中國運籌學會第九屆學術交流會論文集[C];2008年

中國博士學位論文全文數據庫 前6條

1 劉紅衛(wèi);半定規(guī)劃及其應用[D];西安電子科技大學;2002年

2 烏彩英;互補問題與半定規(guī)劃算法研究[D];內蒙古大學;2009年

3 李陽;求解非凸半定規(guī)劃的一類非線性Lagrange方法[D];大連理工大學;2009年

4 田君楊;基于矩量理論的電力系統(tǒng)全局優(yōu)化算法研究[D];廣西大學;2014年

5 李慶娜;最優(yōu)低秩相關系數矩陣問題[D];湖南大學;2010年

6 祝宇楠;凸規(guī)劃技術在水火聯(lián)合調度問題中的應用[D];廣西大學;2014年

中國碩士學位論文全文數據庫 前10條

1 田苗;半定規(guī)劃的光滑化方法研究[D];西安電子科技大學;2008年

2 蔣耀偉;半定規(guī)劃及其應用研究[D];西安電子科技大學;2009年

3 李蕊;半定規(guī)劃的外梯度法研究[D];西安電子科技大學;2010年

4 徐鳳敏;半定規(guī)劃的算法及其在組合優(yōu)化中的應用[D];西安電子科技大學;2001年

5 王淑華;半定規(guī)劃的算法研究[D];西安電子科技大學;2005年

6 王建宏;復半定規(guī)劃及其在系統(tǒng)和控制理論中的應用[D];上海交通大學;2007年

7 褚洪生;最優(yōu)值意義下半定規(guī)劃反問題的結構與求解[D];河北工業(yè)大學;2007年

8 馮昌利;半定規(guī)劃問題的若干算法研究[D];遼寧工程技術大學;2011年

9 李敬玉;解半定規(guī)劃的兩種數值方法[D];青島大學;2011年

10 李思琦;半定規(guī)劃原始對偶內點算法的復雜度分析[D];渤海大學;2015年

，

本文編號：614105