兩類非凸全局優(yōu)化問題的分支定界算法.pdf

1、ABRANCHANDBoUNDALGORITHMFORTWOCLASSESOFNON—CONVEXGLOBALoPTIMIZATIoNPROBLEMSADissertationSubmittedtotheGraduateSchoolofHenanNormalUniversityinPartialFulfillmentoftheRequirementsfortheDegreeofMasterofScienceByWangJunhuaSup

2、ervisor：ProfShenPeipingApril，2011r摘要近年來隨著科學(xué)技術(shù)，尤其是信息技術(shù)的發(fā)展，全局優(yōu)化問題已經(jīng)廣泛應(yīng)用于經(jīng)濟計劃、網(wǎng)絡(luò)與運輸、圖像處理、數(shù)據(jù)庫和芯片設(shè)計、分子生物學(xué)、環(huán)境工程、核能和機械設(shè)計、金融和固定費用等眾多領(lǐng)域中但是，全局優(yōu)化問題往往具有多個不是全局最優(yōu)解的局部最優(yōu)解因此，求解此類問題具有重要意義和極大的挑戰(zhàn)性在已有理論的基礎(chǔ)上，本文針對兩類非凸全局優(yōu)化問題，研究新的有效的求解方法主要內(nèi)容如下：

3、第一章，簡述幾種主要的求解全局優(yōu)化問題的確定性和隨機性方法，及它們的研究現(xiàn)狀，并簡單介紹本文所作的主要工作第二章，針對帶有反凸約束的凸比凹比式和問題(NRP)，提出—個全局優(yōu)化分支定界算法首先，將問題(NRP)轉(zhuǎn)化為一個等價問題，然后利用Lagrange弱對偶理論將下界問題轉(zhuǎn)化為求解一系列的線性規(guī)劃問題，根據(jù)下界問題的對偶信息，可以獲得原問題的可行解，從而用于更新上界最后，我們給出算法的收斂性分析和數(shù)值試驗結(jié)果，并證明所提出算法能有效解

4、決問題(NRP)本算法的優(yōu)點是：主要的計算工作是求解一系列線性規(guī)劃子問題，并且這些子問題隨著迭代次數(shù)的增加其規(guī)模并不擴大第三章，針對一類帶多乘積約束的非凸二次規(guī)劃問題(QP)，提出一種求其全局最優(yōu)解的單純形分支和對偶定界算法該算法首先構(gòu)造—個等價問題，然后利用Lagrange對偶理論將其中關(guān)鍵的定界問題轉(zhuǎn)化為一系列易于求解的線性規(guī)劃問題，最后給出的收斂性分析和數(shù)值算例結(jié)果證明了提出的算法是可行的關(guān)鍵詞：全局優(yōu)化，分支定界，分式規(guī)劃，反凸