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

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

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

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