  We develop a novel unified randomized block-coordinate primal-dual algorithm
to solve a class of nonsmooth constrained convex optimization problems, which
covers different existing variants and model settings from the literature. We
prove that our algorithm achieves optimal $\mathcal{O}(n/k)$ and
$\mathcal{O}(n^2/k^2)$ convergence rates (up to a constant factor) in two
cases: general convexity and strong convexity, respectively, where $k$ is the
iteration counter and n is the number of block-coordinates. Our convergence
rates are obtained through three criteria: primal objective residual and primal
feasibility violation, dual objective residual, and primal-dual expected gap.
Moreover, our rates for the primal problem are on the last iterate sequence.
Our dual convergence guarantee requires additionally a Lipschitz continuity
assumption. We specify our algorithm to handle two important special cases,
where our rates are still applied. Finally, we verify our algorithm on two
well-studied numerical examples and compare it with two existing methods. Our
results show that the proposed method has encouraging performance on different
experiments.
