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