利用模糊次梯度算法求解拉格朗日松弛对偶问题  

Fuzzy subgradient algorithm for solving Lagrangian relaxation dual problem

作　　者：周威[1] 金以慧[1] 

机构地区：[1]清华大学自动化系,北京100084

出　　处：《控制与决策》2004年第11期1213-1217,共5页Control and Decision

基　　金：国家自然科学基金资助项目(60174046).

摘　　要：针对利用次梯度算法处理拉格朗日松弛对偶问题时,计算过程容易出现振荡,求解效率较低的问题,首先提出了一种基于模糊理论的次梯度算法,利用隶属度函数给出迭代过程中所有次梯度的合适权重,并将它们线性加权得到新的迭代方向;其次证明了算法的收敛性;最后通过仿真实验验证了该方法的有效性.To the problem of zigzaging happened in solving the undifferential Lagrangian dual problems by subgradient algorithm, a subgradient algorithm based on fuzzy theory is presented. In this method, the resulting subgradient direction is attained by combining all history subgradient directions, which are achieved in the iteration process, following a simple membership function. The resulting subgradient direction uses the history information suitably, thereby significantly reduces the solution zigzagging difficulty without much additional computational requirements. The convergence of the algorithm is proved. This method is then applied in the traveling salesman problem, and the results show that this method leads to significant improvement over the traditional subgradient algorithm.

关 键 词：拉格朗日松弛 次梯度算法 模糊理论 对偶 

分 类 号：O232[理学—运筹学与控制论]