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

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

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

• 摘要3-4
• Abstract4-8
• 第一章 緒論8-13
• 1.1 問題提出及應用背景8-10
• 1.2 研究現(xiàn)狀、困難及挑戰(zhàn)10-11
• 1.3 本文的主要結(jié)果11-13
• 第二章 0-1二次規(guī)劃文獻綜述13-23
• 2.1 無約束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é)束語與展望36-37
• 參考文獻37-41
• 致謝41-42
• 攻讀學位期間發(fā)表的學術(shù)論文42

【相似文獻】

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

1 吳秉惠;二次規(guī)劃的分解問題[J];國防科技大學學報;1985年03期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

中國重要報紙全文數(shù)據(jù)庫 前1條

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

7 董彥誠;一類二次規(guī)劃反問題的研究[D];大連理工大學;2007年

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

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

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

本文編號：1033254