  We are interested in solving convex optimization problems with large numbers
of constraints. Randomized algorithms, such as random constraint sampling, have
been very successful in giving nearly optimal solutions to such problems. In
this paper, we combine random constraint sampling with the classical
primal-dual algorithm for convex optimization problems with large numbers of
constraints, and we give a convergence rate analysis. We then report numerical
experiments that verify the effectiveness of this algorithm.
