On the convergence rate of dual ascent methods for linearly constrained convex minimization

The authors analyze the rate of convergence of certain dual ascent methods for the problem of minimizing a strictly convex essentially smooth function subject to linear constraints. Included in the present study are dual coordinate ascent methods and dual gradient methods. They show that, under mild assumptions on the problem, these methods attain a linear rate of convergence. The proof is based on estimating the distance for a feasible dual solution to the optimal dual solution set by the norm of a certain residual.