拉格朗日松弛对偶问题的一个改进次梯度算法

摘要：

拉格朗日松弛法是处理整数优化问题的一个重要方法。针对利用次梯度算法求解拉格朗日松弛对偶问题时容易出现收敛速度较慢及计算效率低等问题，对次梯度算法进行了改进：结合当前次梯度和历史次梯度的线性组合给出新的迭代方向，然后决定合适步长。同时证明了算法的收敛性及有效的消除迭代过程中的锯齿现象。将改进的拉格朗日松弛的次梯度算法用于解决 TSP 问题，数值计算结果表明，改进的次梯度算法比普通次梯度算法收敛较快，说明了改进算法的有效性。

关键词：拉格朗日松弛算法、次梯度、优化问题、对偶

所属期刊栏目：13

分类号：O221(运筹学)

资助基金：国家自然科学基金项目71201064。

在线出版日期：2016-05-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1-5