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

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

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

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