資源描述：
《利用模糊次梯度算法求解拉格朗日松弛對偶問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、第19卷第11期控制與決策2004年11月Vol.19No.11ControlandDecisionNov.2004文章編號:100120920(2004)1121213205利用模糊次梯度算法求解拉格朗日松弛對偶問題周威,金以慧(清華大學(xué)自動化系,北京100084)摘要:針對利用次梯度算法處理拉格朗日松弛對偶問題時,計算過程容易出現(xiàn)振蕩,求解效率較低的問題,首先提出了一種基于模糊理論的次梯度算法,利用隸屬度函數(shù)給出迭代過程中所有次梯度的合適權(quán)重,并將它們線性加權(quán)得到新的迭代方向;其次證明了算法的收斂性;最后通過仿真實驗驗證了該
2、方法的有效性.關(guān)鍵詞:拉格朗日松弛;次梯度算法;模糊理論;對偶中圖分類號:O232文獻標(biāo)識碼:AFuzzysubgradientalgorithmforsolvingLagrangianrelaxationdualproblemZHOUWei,JINYi2hui(DepartmentofAutomation,TsinghuaUniversity,Beijing100084,China.Correspondent:ZHOUWei,E2mail:zhouw99@mails.tsinghua.edu.cn)Abstract:Tothe
3、problemofzigzaginghappenedinsolvingtheundifferentialLagrangiandualproblemsbysubgradi2entalgorithm,asubgradientalgorithmbasedonfuzzytheoryispresented.Inthismethod,theresultingsubgradientdirectionisattainedbycombiningallhistorysubgradientdirections,whichareachievedinth
4、eiterationprocess,fol2lowingasimplemembershipfunction.Theresultingsubgradientdirectionusesthehistoryinformationsuitably,therebysignificantlyreducesthesolutionzigzaggingdifficultywithoutmuchadditionalcomputationalrequirements.Theconvergenceofthealgorithmisproved.Thism
5、ethodisthenappliedinthetravelingsalesmanproblem,andtheresultsshowthatthismethodleadstosignificantimprovementoverthetraditionalsubgradientalgorithm.Keywords:Lagrangianrelaxation;subgradientalgorithm;fuzzytheory;dual1引言所有歷史次梯度信息時的收斂條件;[3]提出了正交在拉格朗日松弛算法(LR)中,拉格朗日對偶問次梯度算
6、法,其利用了上一次迭代的次梯度的信息;題的優(yōu)化非常關(guān)鍵,其解決方法通常采用次梯度算[4]則利用了所有的歷史次梯度信息,并采用一個二法.但它不是一種單調(diào)遞減算法,在優(yōu)化過程中容易元二次優(yōu)化問題選擇權(quán)重,但這極大地增加了計算出現(xiàn)振蕩現(xiàn)象,效率較低.一般認為,這是由于它的復(fù)雜度.[1,2]本文將模糊的概念引入次梯度的求取中,提出馬爾可夫?qū)傩栽斐傻?即當(dāng)前次梯度對以前迭代產(chǎn)生的歷史次梯度沒有記憶效應(yīng).對此,已提出一了一種模糊次梯度算法.該算法利用隸屬度函數(shù)給些利用歷史次梯度信息的算法:文獻[2]給出了利用出所有歷史次梯度的對應(yīng)系數(shù),從而
7、“模糊地”利用收稿日期:2003212216;修回日期:2004203211.基金項目:國家自然科學(xué)基金資助項目(60174046).作者簡介:周威(1977—),男,河南商丘人,博士生,從事供應(yīng)鏈計劃、供應(yīng)鏈調(diào)度和協(xié)調(diào)等研究;金以慧(1936—),女,浙江紹興人,教授,從事流程工業(yè)的綜合自動化、生產(chǎn)過程的建模與控制等研究.1214控制與決策第19卷了所有歷史次梯度信息.證明了該算法的收斂性,并梯度方向越近,則其包含的信息越多,所被賦予的權(quán)給出了利用均衡TSP優(yōu)化問題的仿真結(jié)果.通過與重也越大.基于上述思想,給出定義如下(對于j
8、=傳統(tǒng)次梯度算法的比較,表明了該算法的有效性.1,?,k):2算法描述設(shè)第j次迭代得到的對偶值為T對于一個帶約束的最小化問題L(uj,xj)=minL(uj,x)=gjuj+cj.(4)x∈D(P):minf(x),其中:gj=g(xj),cj=f(xj).s.
