Gradient computation of multivariate distribution functions calls for considerable effort. A standard procedure is component-wise computation, hence coordinate descent is an attractive choice. This paper deals with constrained convex problems. We apply random coordinate descent in an approximation scheme that is an inexact cutting-plane method from a dual viewpoint. We present convergence proofs and a computational study.