资源描述：
《利用模糊次梯度算法求解拉格朗日松弛对偶问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第19卷第11期控制与决策2004年11月Vol.19No.11ControlandDecisionNov.2004文章编号:100120920(2004)1121213205利用模糊次梯度算法求解拉格朗日松弛对偶问题周威,金以慧(清华大学自动化系,北京100084)摘要:针对利用次梯度算法处理拉格朗日松弛对偶问题时,计算过程容易出现振荡,求解效率较低的问题,首先提出了一种基于模糊理论的次梯度算法,利用隶属度函数给出迭代过程中所有次梯度的合适权重,并将它们线性加权得到新的迭代方向;其次证明了算法的收敛性;最后通过仿真实验验证了该
2、方法的有效性.关键词:拉格朗日松弛;次梯度算法;模糊理论;对偶中图分类号:O232文献标识码: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、法,其利用了上一次迭代的次梯度的信息;题的优化非常关键,其解决方法通常采用次梯度算[4]则利用了所有的历史次梯度信息,并采用一个二法.但它不是一种单调递减算法,在优化过程中容易元二次优化问题选择权重,但这极大地增加了计算出现振荡现象,效率较低.一般认为,这是由于它的复杂度.[1,2]本文将模糊的概念引入次梯度的求取中,提出马尔可夫属性造成的,即当前次梯度对以前迭代产生的历史次梯度没有记忆效应.对此,已提出一了一种模糊次梯度算法.该算法利用隶属度函数给些利用历史次梯度信息的算法:文献[2]给出了利用出所有历史次梯度的对应系数,从而
7、“模糊地”利用收稿日期:2003212216;修回日期:2004203211.基金项目:国家自然科学基金资助项目(60174046).作者简介:周威(1977—),男,河南商丘人,博士生,从事供应链计划、供应链调度和协调等研究;金以慧(1936—),女,浙江绍兴人,教授,从事流程工业的综合自动化、生产过程的建模与控制等研究.1214控制与决策第19卷了所有历史次梯度信息.证明了该算法的收敛性,并梯度方向越近,则其包含的信息越多,所被赋予的权给出了利用均衡TSP优化问题的仿真结果.通过与重也越大.基于上述思想,给出定义如下(对于j
8、=传统次梯度算法的比较,表明了该算法的有效性.1,⋯,k):2算法描述设第j次迭代得到的对偶值为T对于一个带约束的最小化问题L(uj,xj)=minL(uj,x)=gjuj+cj.(4)x∈D(P):minf(x),其中:gj=g(xj),cj=f(xj).s.
