本文關(guān)鍵詞：半定規(guī)劃的不可行內(nèi)點(diǎn)算法

  更多相關(guān)文章： 半定規(guī)劃 不可行內(nèi)點(diǎn)法 迭代復(fù)雜度 單調(diào)互補(bǔ)問(wèn)題 全牛頓步

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

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

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

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

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

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

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

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

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

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

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

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

10 關(guān)秀翠,刁在筠;半定規(guī)劃的逆問(wèn)題[J];經(jīng)濟(jì)數(shù)學(xué);1999年03期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前7條

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

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

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

4 王曉敏;劉靈;;半定規(guī)劃的原始-對(duì)偶不可行內(nèi)點(diǎn)算法[A];2006年中國(guó)運(yùn)籌學(xué)會(huì)數(shù)學(xué)規(guī)劃分會(huì)代表會(huì)議暨第六屆學(xué)術(shù)會(huì)議論文集[C];2006年

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

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

7 田媛;田志遠(yuǎn);;解半定規(guī)劃問(wèn)題的Log-Sigmoid乘子法[A];中國(guó)運(yùn)籌學(xué)會(huì)第九屆學(xué)術(shù)交流會(huì)論文集[C];2008年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前6條

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

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

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

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

5 李慶娜;最優(yōu)低秩相關(guān)系數(shù)矩陣問(wèn)題[D];湖南大學(xué);2010年

6 祝宇楠;凸規(guī)劃技術(shù)在水火聯(lián)合調(diào)度問(wèn)題中的應(yīng)用[D];廣西大學(xué);2014年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

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

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

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

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

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

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

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

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

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

10 李思琦;半定規(guī)劃原始對(duì)偶內(nèi)點(diǎn)算法的復(fù)雜度分析[D];渤海大學(xué);2015年

，

本文編號(hào)：614105