本文關(guān)鍵詞：基于SDP松弛的0-1二次規(guī)劃全局算法

  更多相關(guān)文章： 0-1二次規(guī)劃 SDP松弛 矩陣分解 片段線性逼近 分枝定界算法

【摘要】：0-1二次規(guī)劃是整數(shù)規(guī)劃中一類(lèi)重要的最優(yōu)化問(wèn)題,廣泛應(yīng)用于工程、經(jīng)濟(jì)管理、金融和管理科學(xué)等許多重要領(lǐng)域,是近年來(lái)國(guó)際優(yōu)化領(lǐng)域中重要而富有挑戰(zhàn)性的課題。近年來(lái)半定規(guī)劃(簡(jiǎn)記SDP)方法的發(fā)展更促進(jìn)了0-1二次規(guī)劃研究。本文研究0-1二次規(guī)劃的SDP松弛和全局算法。我們給出了基于矩陣分解方法的緊SDP松弛,給出了基于SDP松弛的分枝定界算法。以下是本文的主要工作：(1)利用矩陣分解方法,給出了帶線性約束0-1二次規(guī)劃的一個(gè)緊的SDP松弛。通過(guò)目標(biāo)函數(shù)的矩陣分解并利用二次項(xiàng)的片段線性逼近技術(shù),得到了原問(wèn)題的一個(gè)凸松弛。證明了尋找凸松弛中的最優(yōu)參數(shù)問(wèn)題可以歸結(jié)為一個(gè)SDP問(wèn)題。數(shù)值結(jié)果表明該SDP松弛能提供原問(wèn)題的一個(gè)更緊的下界。(2)給出了帶線性約束0-1二次規(guī)劃的基于SDP松弛的分枝定界算法及其收斂性。首先,給出原問(wèn)題和SDP松弛問(wèn)題的最優(yōu)值之間的關(guān)系。其次,給出基于SDP松弛的一個(gè)新的分枝定界算法,證明算法在有限步內(nèi)收斂于問(wèn)題全局最優(yōu)解。初步數(shù)值結(jié)果表明我們所提出的算法能有效地找到問(wèn)題全局最優(yōu)解。
【關(guān)鍵詞】：0-1二次規(guī)劃 SDP松弛 矩陣分解 片段線性逼近 分枝定界算法
【學(xué)位授予單位】：浙江工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：O221.4
【目錄】：

• 摘要3-4
• Abstract4-8
• 第一章 緒論8-13
• 1.1 問(wèn)題提出及應(yīng)用背景8-10
• 1.2 研究現(xiàn)狀、困難及挑戰(zhàn)10-11
• 1.3 本文的主要結(jié)果11-13
• 第二章 0-1二次規(guī)劃文獻(xiàn)綜述13-23
• 2.1 無(wú)約束0-1二次規(guī)劃13-17
• 2.1.1 線性化方法13-14
• 2.1.2 SDP松弛方法14-17
• 2.1.3 凸0-1二次規(guī)劃變換17
• 2.2 約束0-1二次規(guī)劃17-22
• 2.2.1 SDP松弛方法18-19
• 2.2.2 凸0-1二次規(guī)劃變換19-22
• 2.3 0-1二次規(guī)劃的分枝定界方法22-23
• 第三章 基于矩陣分解的0-1二次規(guī)劃SDP松弛23-31
• 3.1 引言23-24
• 3.2 最佳矩陣分解和SDP松弛24-29
• 3.3 數(shù)值結(jié)果29-31
• 第四章 基于SDP松弛的0-1二次規(guī)劃分枝定界算法31-36
• 4.1 引言31-32
• 4.2 分枝定界算法32-33
• 4.3 數(shù)值結(jié)果33-36
• 第五章 結(jié)束語(yǔ)與展望36-37
• 參考文獻(xiàn)37-41
• 致謝41-42
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文42

【相似文獻(xiàn)】

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

1 吳秉惠;二次規(guī)劃的分解問(wèn)題[J];國(guó)防科技大學(xué)學(xué)報(bào);1985年03期

2 李明霞,黃石清,蔡奇志;解某一特殊二次規(guī)劃的一個(gè)算法[J];高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào);1989年01期

3 隋允康;完全二階的“二次規(guī)劃”的一種解法[J];工程數(shù)學(xué)學(xué)報(bào);1990年03期

4 巴達(dá)拉胡;一類(lèi)參數(shù)二次規(guī)劃參數(shù)延拓的作用集法和穩(wěn)定性分析[J];高校應(yīng)用數(shù)學(xué)學(xué)報(bào)A輯(中文版);1997年01期

5 劉小冬,張勝貴,胡國(guó)雷;正定二次規(guī)劃的一個(gè)對(duì)偶算法[J];純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué);2000年04期

6 胡國(guó)雷;求解大規(guī)模帶二次簡(jiǎn)單約束的二次規(guī)劃的顯式自調(diào)比投影收縮算法[J];高等學(xué)校計(jì)算數(shù)學(xué)學(xué)報(bào);2001年04期

7 鐘萬(wàn)勰,張洪武;二次規(guī)劃的混合能方法及桿系結(jié)構(gòu)彈塑性分析[J];固體力學(xué)學(xué)報(bào);2002年02期

8 王新輝,劉三陽(yáng),劉紅衛(wèi);最大割問(wèn)題的二次規(guī)劃方法(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2003年04期

9 田小麗;李煒;蔡逸凡;;完全型區(qū)間系數(shù)二次規(guī)劃的數(shù)值解法[J];杭州電子科技大學(xué)學(xué)報(bào);2008年01期

10 朱劍森 ,喬新;用序列二次規(guī)劃作復(fù)合材料結(jié)構(gòu)的優(yōu)化設(shè)計(jì)[J];南京航空航天大學(xué)學(xué)報(bào);1985年03期

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

1 黃鋒;王彩華;;工程結(jié)構(gòu)的序列模糊二次規(guī)劃[A];中國(guó)系統(tǒng)工程學(xué)會(huì)模糊數(shù)學(xué)與模糊系統(tǒng)委員會(huì)第五屆年會(huì)論文選集[C];1990年

2 張立峰;;一個(gè)求解二次規(guī)劃的微分方程方法[A];第四屆全國(guó)決策科學(xué)/多目標(biāo)決策研討會(huì)論文集[C];2007年

3 石培培;劉紅英;;具有單個(gè)等式和界約束二次規(guī)劃的新算法[A];中國(guó)運(yùn)籌學(xué)會(huì)第八屆學(xué)術(shù)交流會(huì)論文集[C];2006年

4 陳偉;張連生;;整數(shù)二次規(guī)劃的全局最優(yōu)性條件(英文)[A];中國(guó)運(yùn)籌學(xué)會(huì)第八屆學(xué)術(shù)交流會(huì)論文集[C];2006年

5 王其冬;王麗燕;馮恩民;;臨界項(xiàng)目集剖分的雙層規(guī)劃模型及主要性質(zhì)[A];第四屆中國(guó)青年運(yùn)籌與管理學(xué)者大會(huì)論文集[C];2001年

6 劉建信;隋允康;;基于Sigmoid函數(shù)的0-1規(guī)劃變換與解法[A];北京力學(xué)會(huì)第14屆學(xué)術(shù)年會(huì)論文集[C];2008年

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫(kù) 前1條

1 記者 張丹;地區(qū)江落康莎文化產(chǎn)業(yè)項(xiàng)目二次規(guī)劃匯報(bào)會(huì)召開(kāi)[N];日喀則報(bào)(漢);2014年

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

1 穆學(xué)文;{-1，，1}二次規(guī)劃算法及其應(yīng)用研究[D];西安電子科技大學(xué);2006年

2 黎健玲;連續(xù)與離散單調(diào)優(yōu)化和不定二次規(guī)劃算法研究[D];上海大學(xué);2007年

3 肖現(xiàn)濤;求解半定約束二次規(guī)劃逆問(wèn)題的數(shù)值方法[D];大連理工大學(xué);2009年

4 陳偉;0-1二次規(guī)劃的全局最優(yōu)性條件及算法[D];上海大學(xué);2005年

5 唐春明;強(qiáng)次可行方法與序列二次約束二次規(guī)劃算法的研究[D];上海大學(xué);2008年

6 郭曉玲;二次規(guī)劃的線性錐規(guī)劃表示及算法研究[D];清華大學(xué);2014年

7 路程;非負(fù)二次函數(shù)錐規(guī)劃[D];清華大學(xué);2011年

8 胡清潔;求解約束優(yōu)化問(wèn)題的序列二次規(guī)劃方法研究[D];湖南大學(xué);2008年

9 李山春;生產(chǎn)過(guò)程穩(wěn)態(tài)模型的尋優(yōu)方法及應(yīng)用研究[D];中南大學(xué);2011年

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

1 劉瑋;基于線性方程組的無(wú)序列二次規(guī)劃方法的研究[D];河北大學(xué);2015年

2 姜勇;Lasserre松弛方法在二次規(guī)劃中的應(yīng)用[D];湘潭大學(xué);2015年

3 蔡偉榮;基于SDP松弛的0-1二次規(guī)劃全局算法[D];浙江工業(yè)大學(xué);2015年

4 王倩;一種新的正定二次規(guī)劃算法[D];西安科技大學(xué);2011年

5 張璐;大規(guī)模二次規(guī)劃相關(guān)算法的研究[D];遼寧工程技術(shù)大學(xué);2010年

6 樊炳倩;基于距離的正定二次規(guī)劃算法[D];西安科技大學(xué);2012年

7 董彥誠(chéng);一類(lèi)二次規(guī)劃反問(wèn)題的研究[D];大連理工大學(xué);2007年

8 林苗珊;一類(lèi)二次規(guī)劃反問(wèn)題的光滑函數(shù)法[D];大連理工大學(xué);2007年

9 馮婷婷;二次規(guī)劃的并行變量分配算法研究[D];山東科技大學(xué);2011年

10 聞昆侖;一個(gè)有限內(nèi)存序列二次規(guī)劃算法的研究[D];北京交通大學(xué);2012年

本文編號(hào)：1033254