A random coordinate descent method for large-scale resource allocation problems

In this paper we develop a randomized (block) coordinate descent method for solving singly linear equality constrained optimization problems that appear for example in resource allocation over networks. We show that for strongly convex objective functions the new algorithm has an expected linear convergence rate that depends on the second smallest eigenvalue λ₂(Q) of a matrix Q that is defined in terms of the probabilities and the number of blocks. However, the computational complexity per iteration of our method is much simpler than of a method based on full gradient information. We also focus on how to choose the probabilities to make this randomized algorithm to converge as fast as possible and we arrive at solving a sparse SDP. Finally, we present some numerical results for our method that show its efficiency on huge sparse problems.