基于随机加速对偶下降算法的分布式网络流量优化

发布时间：2018-05-17 23:03

本文选题：加速对偶下降算法 + 随机加速对偶下降(ADD)算法　；参考：《重庆邮电大学学报(自然科学版)》2014年06期

【摘要】：传统的分布式网络流量优化问题大都通过对偶梯度下降算法来解决,虽然该算法能够以分布式方式来实现,但其收敛速度较慢。加速对偶下降(accelerated dual descent,ADD)算法通过近似牛顿步长的分布式计算,提高了对偶梯度下降算法的收敛速率。但由于通信网络的不确定性,在约束不确定时,该算法的收敛性难以保证。基于此,提出了一种随机形式的ADD算法来解决该网络优化问题。理论上证明了随机ADD算法在不确定性的均方误差有界时,能以较高概率收敛于最优值的一个误差邻域;当给出更严格的不确定性的约束条件时,算法则可以较高概率收敛于最优值。实验结果表明,随机ADD算法的收敛速率比随机梯度下降算法快2个数量级。
[Abstract]:The traditional distributed network traffic optimization problem is mostly solved by dual gradient descent algorithm. Although the algorithm can be implemented in a distributed way, its convergence rate is slow. The convergence rate of the dual gradient descent algorithm is improved by the distributed computation of the approximate Newtonian step size for the accelerated dual descent dual descented algorithm. However, due to the uncertainty of the communication network, the convergence of the algorithm is difficult to guarantee when the constraints are uncertain. Based on this, a stochastic ADD algorithm is proposed to solve the network optimization problem. It is theoretically proved that the stochastic ADD algorithm can converge to an error neighborhood of the optimal value with a higher probability when the mean square error of the uncertainty is bounded, and when the more strict constraint conditions of uncertainty are given, The algorithm can converge to the optimal value with higher probability. Experimental results show that the convergence rate of the stochastic ADD algorithm is two orders of magnitude faster than that of the stochastic gradient descent algorithm.
【作者单位】：重庆电子工程职业学院计算机学院;
【分类号】：TN915.06

【参考文献】