论文部分内容阅读
考虑一类约束优化问题.交通调控，机器学习等领域的许多重要问题本质上都是线性约束问题.最近的研究发现对偶上升算法对于一类等式约束优化问题取得了很好的效果.本文介绍了对偶上升法和双步对偶上升法并且将这两种算法推广到更加一般的线性约束优化问题上.文章证明了上述两种算法对于更一般的情况也是收敛的，且收敛速率分别为O(1/k)和O（1/k2）.为了解决这些约束优化问题，我们重新将原问题改写为没有约束条件的对偶问题并应用上述的算法.对矩阵矫正问题和最小二乘问题的数值实验证明对偶上升法非常高效.另一方面，我们的数值试验说明，理论上更好的O(1/k2)算法，计算实践并没有O(1/k)的方法好.