Convergence Rates of Min-Cost Subgraph Algorithms for Multicast in Coded Networks

Abstract — The problem of establishing minimum-cost mul-ticast connections in coded networks can be viewed as an optimization problem, and decentralized algorithms were pro-posed by Lun et. al. to compute the optimal subgraph using the subgradient method on the dual problem. However, the convergence rate problem for these algorithms remains open. In general, there are results available for the convergence rate of the subgradient method on the dual problem, but it is hard to find the convergence rate of the primal solutions. In this paper, we analyze the convergence rates of the min-cost subgraph algorithms for both the dual and the primal sides. We show that using the incremental subgradient method on the dual problem with appropriately chosen step sizes yields linear convergence rate to a neighborhood of the optimal solution. Also, if we use constant step sizes in the subgradient method and simple averaging for primal recovery, the primal solutions recovered from the dual iterations converge to a neighborhood of the optimal solution with rate O(1/n). I