摘要
拉格朗日松弛法的关键是求解对偶函数,而在对偶函数不可微的情况下人们经常采用次梯度法,为此提出一种变直径次梯度投影法.该方法根据投影性质确定对偶问题定义域的有效直径,从而使其收敛性不依赖于最优目标值和对偶问题定义域直径等任何先验知识,并证明了其收敛性,给出了收敛效率.通过一个指派问题说明了所提出方法的有效性.
A key step of Lagrangian relaxation is to optimize the dual function, and the subgradient method is frequently used when the dual function is nondifferentiable. A subgradient projection method with variable diameter is presented for the dual function of constrained programming. The efficient diameter of the dual function is determined according to the projection properties, consequently the convergence of the method is independent of any prior knowledge such as the optimal value, the diameter of the dual function definition domain, etc. The convergence is proved, and the efficiency of it is given. A numerical test on an assignment problem shows the efficiency of the method.
出处
《控制与决策》
EI
CSCD
北大核心
2004年第3期303-306,共4页
Control and Decision
基金
国家自然科学基金资助项目(60174046).
关键词
对偶
次梯度投影
变直径
Algorithms
Error analysis
Gradient methods
