本文關(guān)鍵詞：雙線性規(guī)劃問題的凸松弛求解方法研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：對大部分求最小值的二次約束二次規(guī)劃問題來說,若其目標(biāo)函數(shù)是非凸的,或者約束中存在非凸的約束條件,這個問題是NP-hard的。在本文中,我們主要關(guān)注二次約束二次規(guī)劃中的一類特殊問題  雙線性規(guī)劃問題。本文的主要工作是提出雙線性規(guī)劃問題的一個非多項式時間求解算法。雙線性規(guī)劃問題(BP)是一類特殊的二次約束二次規(guī)劃問題(QCQP),這類問題是NP-hard問題。雙線性模型在現(xiàn)實中有許多應(yīng)用:生產(chǎn)規(guī)劃,動態(tài)識別,多代理規(guī)劃等其他問題都可以被描述成雙線性模型來求解。盡管近年來人們提出了很多求解二次約束二次規(guī)劃問題的高效算法,但是專門針對雙線性模型的算法很少被人關(guān)注。雖然我們可以用求解二次規(guī)劃問題的通用算法來求解雙線性規(guī)劃問題,但是考慮到雙線性模型的特殊結(jié)構(gòu),這將加大問題的維度,降低算法的效率。針對這一情況,本文的主要工作是提出了一個利用雙線性規(guī)劃問題的結(jié)構(gòu)來對其求解的凸松弛迭代算法。算法的主要思路是借助雙線性規(guī)劃問題目標(biāo)函數(shù)中的交叉項矩陣的奇異值分解,將一個雙線性規(guī)劃問題變形成了一個二次規(guī)劃問題。之后,采用凸包松弛的方法來處理變形后的二次規(guī)劃問題。經(jīng)過一系列變形,算法最終得到了原問題的一個凸的二次約束二次規(guī)劃松弛問題,這是一個可在多項式時間內(nèi)求解的問題。與原問題相比,這個松弛問題中引入了O(n)個附加變量和線性約束。將這個凸松弛問題嵌入分支定界算法中,能夠得到原雙線性規(guī)劃問題全局最優(yōu)值的上界和下界序列。文章的第二部分主要證明了本文所提出的算法的正確性。我們證明了算法中得到原規(guī)劃問題最優(yōu)值的上界、下界序列將收斂到目標(biāo)函數(shù)的最優(yōu)值,并對求出給定精度范圍內(nèi)全局最優(yōu)解所需的最大迭代步數(shù)做出了估計。文章第三部分展示的數(shù)值實驗結(jié)果驗證了本文提出的算法在求解高維雙線性問題時有更高的效率。本文的創(chuàng)新點主要包括:?通過SVD分解降低了松弛問題的維度。?引入了由目標(biāo)函數(shù)值確定分支策略的分支定界算法。?進行了高維數(shù)值實驗,證明了我們的算法在求解高維問題時更為有效。
【關(guān)鍵詞】：雙線性規(guī)劃 二次約束二次規(guī)劃 SVD分解 分支定界算法
【學(xué)位授予單位】：清華大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：O221
【目錄】：

• 摘要3-4
• Abstract4-8
• 第1章 引言8-13
• 1.1 選題背景和基礎(chǔ)知識8-10
• 1.1.1 研究背景8-9
• 1.1.2 BP問題的分類9-10
• 1.2 研究現(xiàn)狀10-13
• 1.2.1 連續(xù)可分離約束的情況10-11
• 1.2.2 連續(xù)聯(lián)合約束的情況11
• 1.2.3 整數(shù)雙線性規(guī)劃的情況11-13
• 第2章 二次規(guī)劃問題的發(fā)展13-19
• 2.1 非凸二次規(guī)劃問題是NP-hard的13-14
• 2.2 半定規(guī)劃松弛14
• 2.3 協(xié)正錐規(guī)劃變形14-15
• 2.4 線性化重構(gòu)方法15-16
• 2.5 凸包絡(luò)處理技術(shù)16-19
• 第3章 雙線性規(guī)劃問題的二次規(guī)劃松弛問題求解辦法19-27
• 3.1 二次規(guī)劃變形19-20
• 3.2 二次約束二次規(guī)劃問題的松弛20-21
• 3.3 分支定界算法21-23
• 3.4 主要定理23-27
• 第4章 關(guān)于二次松弛和線性松弛的數(shù)值實驗對比27-35
• 第5章 延伸與總結(jié)35-38
• 5.1 二次規(guī)劃求解延伸35-36
• 5.2 總結(jié)36-38
• 致謝38-40
• 個人簡歷、在學(xué)期間發(fā)表的學(xué)術(shù)論文與研究成果40

【相似文獻(xiàn)】

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

1 陳高波,劉海燕,商勝武;一類雙線性規(guī)劃的線性逼近算法[J];西南交通大學(xué)學(xué)報;2002年05期

2 ;[J];;年期

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

1 高岳林;雷崇民;馬小華;;一種連接雙線性規(guī)劃問題的整體優(yōu)化[A];中國運籌學(xué)會第七屆學(xué)術(shù)交流會論文集（中卷）[C];2004年

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

1 姜珊;雙線性規(guī)劃問題的凸松弛求解方法研究[D];清華大學(xué);2015年

  本文關(guān)鍵詞：雙線性規(guī)劃問題的凸松弛求解方法研究，由筆耕文化傳播整理發(fā)布。

本文編號：275473