【摘要】 在基于拉格朗日松弛法(LR)的优化调度算法中,对偶问题的求解广泛采用的一种方法是次梯度法。在这个方法中,为了得到一个次梯度方向,相应松弛问题的所有的子问题都必须精确求解,当问题规模较大时求解时间过长。讨论了逐步次梯度法求解对偶问题的具体实现方法。将对偶函数化为多个子项和的形式,每求解一个子问题,就构造对应对偶函数一个子项的次梯度,逐步沿这些次梯度方向更新乘子。仿真结果显示,其收敛速度较原始的次梯度法有明显的提高。更多还原

【Abstract】 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 results show that the incremental subgradient method leads to significant improvement in terms of computational efficiency compared with the standard subgradient method.更多还原