  In this paper we propose a variant of the random coordinate descent method
for solving linearly constrained convex optimization problems with composite
objective functions. If the smooth part of the objective function has Lipschitz
continuous gradient, then we prove that our method obtains an
$\epsilon$-optimal solution in ${\cal O}(N^2/\epsilon)$ iterations, where $N$
is the number of blocks. For the class of problems with cheap coordinate
derivatives we show that the new method is faster than methods based on
full-gradient information. Analysis for the rate of convergence in probability
is also provided. For strongly convex functions our method converges linearly.
Extensive numerical tests confirm that on very large problems, our method is
much more numerically efficient than methods based on full gradient
information.
