Network optimization under uncertain constraints with stochastic ADD algorithms
LI Dong-me · 2014
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.