逐步次梯度法在基于LR的调度算法中的应用  

Incremental Subgradient Method to Scheduling Algorithm Based on Lagrangian Relaxation

作　　者：陶继平[1] 徐文艳[2] 王豪[1] 

机构地区：[1]上海交通大学自动化系,上海200240 [2]上海师范大学生命与环境科学学院,上海200234

出　　处：《控制工程》2007年第5期566-568,共3页Control Engineering of China

摘　　要：在基于拉格朗日松弛法(LR)的优化调度算法中,对偶问题的求解广泛采用的一种方法是次梯度法。在这个方法中,为了得到一个次梯度方向,相应松弛问题的所有的子问题都必须精确求解,当问题规模较大时求解时间过长。讨论了逐步次梯度法求解对偶问题的具体实现方法。将对偶函数化为多个子项和的形式,每求解一个子问题,就构造对应对偶函数一个子项的次梯度,逐步沿这些次梯度方向更新乘子。仿真结果显示,其收敛速度较原始的次梯度法有明显的提高。The standard subgradient optimization method is one of the most widely adopted algorithm for solving the dual problem arising in scheduling algorithm based on Lagrangian relaxation. In the method, all subproblems of the relaxed problem must be solved in order to obtain a subgradient direction. The incremental subgradient method is applied, where the dual function is transformed into the sum of many component functions, then the subgradient iteration is performed incrementally along the subgradient of every component function obtained by solving the corresponding subproblem. The simulation resuhs show that the incremental subgradient method leads to significant improvement in terms of computational efficiency compared with the standard subgradient method.

关 键 词：调度 拉格朗日松弛法 次梯度 逐步次梯度法 

分 类 号：TP13[自动化与计算机技术—控制理论与控制工程]