We develop a novel algorithm for sparse Stokes parameters imaging in radio interferometry under the polarization constraint. The latter is a physical non-linear relation between the Stokes parameters, imposing the polarization intensity as a lower bound on the total intensity. To solve the joint inverse Stokes imaging problem including this bound, we leverage epigraphical projection techniques in convex optimization and design a primal-dual method offering a highly flexible and parallelizable structure. In addition, we propose to regularize each Stokes parameter map through an average sparsity prior in the context of a reweighted analysis approach (SARA). The resulting approach is dubbed Polarized SARA. We demonstrate on simulated observations of M87 with the Event Horizon Telescope that imposing the polarization constraint leads to superior image quality. For the considered datasets, the results also indicate better performance of the average sparsity prior in comparison with the widely used Cotton-Schwab CLEAN algorithm and other total variation based priors for polarimetric imaging.