随机ADD算法的不确定网络优化研究

Network optimization under uncertain constraints with stochastic ADD algorithms

传统的网络优化问题通过对偶梯度下降算法来解决,虽然该算法能够以分布式方式来实现,但其收敛速度较慢。加速对偶下降算法(ADD)通过近似牛顿步长的分布式计算,提高了对偶梯度下降算法的收敛速率。但由于通信网络的不确定性,在约束不确定时,该算法的收敛性难以保证。基于此,提出了一种随机形式的ADD算法来解决该网络优化问题。理论上证明了随机ADD算法当不确定性的均方误差有界时,能以较高概率收敛于最优值的一个误差邻域;当给出更严格的不确定性的约束条件时,算法则可以较高概率收敛于最优值。实验结果表明,随机ADD算法的收敛速率比随机梯度下降算法快两个数量级。

Traditional network optimization problems are always solved by the dual gradient descent algorithm,which although can be implemented in a distributed manner,has a slow convergence rate. The accelerated dual descent（ ADD） algorithms improve the convergence rate of dual gradient descent algorithm through distributed computation of approximated Newton steps.But with the uncertainty of communication networks,the convergence of the algorithm cannot be guaranteed under uncertain constraints. Based on this,this paper proposed a stochastic version of ADD algorithm to solve the network optimization problems under uncertainty. It proved theoretically that the stochastic ADD algorithms could almost surely converge to an error neighborhood of the optimal when the mean square error of the uncertainty was bounded,and gave a more strict constraint of uncertainty,can exactly almost surely converge to the optimal point. Numerical results show that the stochastic ADD algorithms converge in two orders of magnitude less iteration than the stochastic gradient descent algorithms.