Network optimization under uncertainty

Network optimization problems are often solved by dual gradient descent algorithms which can be implemented in a distributed manner but are known to have slow convergence rates. The accelerated dual descent (ADD) method improves this convergence rate by distributed computation of approximate Newton steps. This paper shows that a stochastic version of ADD can be used to solve network optimization problems with uncertainty in the constraints as is typical of communication networks. We prove almost sure convergence to an error neighborhood when the mean square error of the uncertainty is bounded and give a more restrictive sufficient condition for exact almost sure convergence to the optimal point. Numerical experiments show that stochastic ADD converges in two orders of magnitude fewer iterations than stochastic gradient descent.