本文關(guān)鍵詞：二次約束二次規(guī)劃非升維條件下的松弛理論及算法，由筆耕文化傳播整理發(fā)布。

【摘要】：二次約束二次規(guī)劃(QCQP)問題可描述系列離散優(yōu)化和連續(xù)優(yōu)化問題,如組合優(yōu)化中的最大割、最大團(tuán)、0-1二次背包問題,經(jīng)典的線性規(guī)劃、金融投資領(lǐng)域的馬科維茨方差—均值模型等。因此對QCQP問題的研究有著重要的理論和應(yīng)用價值。當(dāng)QCQP問題的目標(biāo)函數(shù)及約束函數(shù)都是凸函數(shù)時,該問題可以結(jié)合內(nèi)點算法在多項式時間內(nèi)求解,但一般的QCQP問題已被證明為NPH問題。針對QCQP問題目前有多個研究熱點,但主要集中在問題的松弛及估界、最優(yōu)解的判定條件、尋找多項式時間內(nèi)的可解子問題類、設(shè)計全局最優(yōu)搜索算法。在一般的QCQP問題的研究中,最常用的工具是SDP松弛和拉格朗日對偶理論,此外也常將RLT不等式加入到SDP松弛中,且往往這種處理方式比單獨用SDP松弛或RLT不等式的效果都要好。本文首先就QCQP問題的研究背景、意義、目前的研究熱點、常用的處理方法進(jìn)行了簡單的介紹,之后本文研究了凸約束下的非凸二次規(guī)劃問題在不升維下的凸松弛方法,并設(shè)計了求解這類QCQP問題全局最優(yōu)解的算法,接著從理論上給出了算法的收斂性及最壞情形下的迭代次數(shù),同時通過求解一些隨機(jī)算例將本文算法同SDP松弛下的分支定界算法進(jìn)行了對比。數(shù)值結(jié)果表明當(dāng)問題維度及負(fù)特征根個數(shù)較少時本文算法具有一定的優(yōu)勢。然后本文研究了有界區(qū)域上的一般的QCQP問題,給出了不升維下松弛原問題的方法,并設(shè)計了分支定界算法且從理論上論證了算法的收斂性和最壞情形下的迭代次數(shù)。最后經(jīng)過數(shù)值實驗表明算法在問題維度較低、負(fù)特征根較少的情形下迭代次數(shù)及運行時間都同SDP松弛下的分支定界算法效果相近,當(dāng)負(fù)特征根增加時本文算法的運行時間會明顯增加。本文主要的創(chuàng)新點如下:(1)針對一般的QCQP問題給出了在不升維的框架下用直線代替凹二次函數(shù)來松弛原問題問題的方法,并通過理論分析設(shè)計了相應(yīng)的分支定界算法搜索原問題的全局最優(yōu)解;(2)從理論上證明了本文設(shè)計的分支定界算法的收斂性及最壞情形下的迭代次數(shù),并分別給出了本文算法、SDP松弛下的分支定界算法以及Baron的數(shù)值實驗結(jié)果且對結(jié)果進(jìn)行了對比分析;
【關(guān)鍵詞】：QCQP問題 SDP松弛 分支定界算法 多項式時間
【學(xué)位授予單位】：清華大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O221.2
【目錄】：

• 摘要3-4
• abstract4-9
• 第1章 引言9-16
• 1.1 QCQP問題的研究背景及意義9-10
• 1.2 QCQP問題目前的研究熱點10-15
• 1.2.1 QCQP問題的松弛方法11-13
• 1.2.2 錐規(guī)劃方法的引入13-14
• 1.2.3 最優(yōu)判定性條件與可解子類14-15
• 1.3 各章節(jié)主要內(nèi)容15-16
• 第2章 凸約束下的非凸二次規(guī)劃16-33
• 2.1 問題的分析和目標(biāo)函數(shù)不升維的松弛處理16-19
• 2.2 松弛問題的分支定界算法19-24
• 2.2.1 分支19-23
• 2.2.2 定界23
• 2.2.3 分支定界算法23-24
• 2.3 算法的有效性分析24-32
• 2.3.1 算法的收斂性及最壞情形迭代次數(shù)24-26
• 2.3.2 算法的實例分析26-32
• 2.4 本章小結(jié)32-33
• 第3章 非凸約束下的非凸二次規(guī)劃33-45
• 3.1 問題的分析及凸化處理33-36
• 3.1.1 變量替換下的松弛33-36
• 3.2 松弛問題的分支定界算法36-41
• 3.2.1 分支36-40
• 3.2.2 定界40
• 3.2.3 終止條件40-41
• 3.2.4 分支定界算法41
• 3.3 算法的有效性分析41-44
• 3.3.1 算法的收斂性及最壞情形迭代次數(shù)42
• 3.3.2 算法的實例分析42-44
• 3.4 本章小結(jié)44-45
• 第4章 總結(jié)45-46
• 參考文獻(xiàn)46-49
• 致謝49-51
• 個人簡歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果51

【相似文獻(xiàn)】

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

1 孫娟;盛紅波;孫小玲;;多約束二次0-1背包問題的分支定界算法(英文)[J];Journal of Shanghai University(English Edition);2007年03期

2 楊夷梅;楊玉軍;;分支定界算法優(yōu)化研究[J];中國科技信息;2008年21期

3 井霞;高岳林;;線性分式和規(guī)劃問題的分母輸出空間分支定界算法[J];河南師范大學(xué)學(xué)報(自然科學(xué)版);2011年04期

4 牛淑芬;王國欣;孫小玲;;離散投資組合多因素模型的一種分支定界算法(英文)[J];Journal of Shanghai University(English Edition);2008年01期

5 楊金勇;宋海洲;;一類非線性比式和問題的分支定界算法[J];華僑大學(xué)學(xué)報(自然科學(xué)版);2014年03期

6 黎健玲;王鵬;馬林;李杰;;求不定二次規(guī)劃問題全局解的新的分支定界算法[J];廣西大學(xué)學(xué)報(自然科學(xué)版);2009年04期

7 周雪剛;;線性乘性規(guī)劃的因式輸出空間分支定界算法[J];青島科技大學(xué)學(xué)報(自然科學(xué)版);2013年06期

8 趙營峰;尹景本;;一類線性多乘積規(guī)劃的分支定界算法[J];河南科技學(xué)院學(xué)報(自然科學(xué)版);2013年03期

9 吳國榮;高岳林;鄧光智;;箱約束李普希茲優(yōu)化問題的一種新的定界算法[J];寧夏大學(xué)學(xué)報(自然科學(xué)版);2008年01期

10 張玉忠;張咸昭;孫志慧;;關(guān)于問題P_m|intree;p_j=1;r_j|C_(max)的分支定界算法[J];運籌學(xué)學(xué)報;2006年02期

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

1 黎健玲;馬林;王鵬;;箱子約束不定二次規(guī)劃的一個分支定界算法(英文)[A];中國運籌學(xué)會第九屆學(xué)術(shù)交流會論文集[C];2008年

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

1 曹先騰;二次約束二次規(guī)劃非升維條件下的松弛理論及算法[D];清華大學(xué);2015年

2 李景陽;基于多線程的并行分支定界算法框架及其應(yīng)用[D];東北大學(xué);2014年

3 秦平平;分支定界算法在運籌學(xué)模型中的應(yīng)用[D];燕山大學(xué);2009年

4 馬艷利;混合整數(shù)非線性規(guī)劃問題的分支定界算法研究[D];寧夏大學(xué);2014年

5 魏飛;幾類非凸規(guī)劃問題的分支定界算法研究[D];北方民族大學(xué);2011年

6 劉泳;基于拉格朗日松弛和分支定界算法的3PL運輸調(diào)度問題[D];華中科技大學(xué);2011年

7 林秀娟;面向入廠物流的可重用資源約束調(diào)度模型及分支定界算法[D];上海交通大學(xué);2014年

8 余其旺;基于分支定界算法的三層決策模型與應(yīng)用研究[D];武漢科技大學(xué);2010年

9 李一明;分支定界算法的分布并行化研究[D];電子科技大學(xué);2006年

10 俞亮;訂貨與發(fā)貨整合批量調(diào)度模型研究[D];上海交通大學(xué);2010年

  本文關(guān)鍵詞：二次約束二次規(guī)劃非升維條件下的松弛理論及算法，由筆耕文化傳播整理發(fā)布。

，

本文編號：375970