廣義多乘積規(guī)劃問題的近似算法.pdf

1、廣義多乘積規(guī)劃問題屬于非凸優(yōu)化問題，可能存在多個非全局的局部極值點，使得求解極具挑戰(zhàn)性.同時廣義多乘積規(guī)劃問題在經(jīng)濟、工程等領(lǐng)域有重要的應(yīng)用價值，近年來，一些學(xué)者利用啟發(fā)性算法求解該問題.啟發(fā)性算法或許能夠獲得最優(yōu)解，然而無法保證其執(zhí)行效率的好壞.因此，從既能保證執(zhí)行效率又能提供運算時間理論分析的角度出發(fā)尋找求解全局優(yōu)化問題的算法已成為當(dāng)前研究者探索的方向.本文針對兩類特殊的多乘積規(guī)劃問題，依據(jù)問題本身具有的特點分別給出了相應(yīng)的近似算法

2、，不僅提供了算法獲得全局近似最優(yōu)解的證明，而且分別給出了算法運算時間的復(fù)雜性結(jié)果.主要內(nèi)容概括如下.
　　第一章簡單介紹了本文考慮的全局優(yōu)化問題以及這些問題的研究背景、研究現(xiàn)狀及研究意義，最后給出了本文的主要工作.
　　第二章主要關(guān)于廣義線性多乘積極小化問題.基于問題本身的特點,首先估計指定目標(biāo)函數(shù)在可行域內(nèi)的上界與下界，進而獲得一個適當(dāng)?shù)暮凶樱ɑ虺匦危?然后沿著盒子的每一個方向按照相同的比例分割形成一個非均勻網(wǎng)格，結(jié)合參

3、量線性化方法，提出一個近似算法.算法的可行性通過數(shù)值結(jié)果被驗證.且本文給出較好的計算復(fù)雜度結(jié)果.
　　第三章主要考慮廣義分式規(guī)劃問題.根據(jù)問題滿足的性質(zhì)，首先通過指定目標(biāo)函數(shù)在可行域內(nèi)的上估計與下估計構(gòu)造一個恰當(dāng)?shù)暮凶?其次從盒子的下估計點沿著對角線搜索網(wǎng)格結(jié)點，進而將原問題轉(zhuǎn)為與網(wǎng)格結(jié)點有關(guān)的子問題.最后通過求解每一個與網(wǎng)格結(jié)點有關(guān)的子問題獲得原問題的近似最優(yōu)解.于是，一個近似算法被提出.本文通過算例結(jié)果表明算法是有效可行的，并