  In this paper, we denoise a given noisy image by minimizing a smoothness
promoting function over a set of local similarity measures which compare the
mean of the given image and some candidate image on a large collection of
subboxes. The associated convex optimization problem possesses a huge number of
constraints which are induced by extended real-valued functions stemming from
the Kullback--Leibler divergence. Alternatively, these nonlinear constraints
can be reformulated as affine ones, which makes the model seemingly more
tractable. For the numerical treatment of both formulations of the model (i.e.,
the original one as well as the one with affine constraints), we propose a
rather general augmented Lagrangian method which is capable of handling the
huge amount of constraints. A self-contained, derivative-free, global
convergence theory is provided, allowing an extension to other problem classes.
For the solution of the resulting subproblems in the setting of our suggested
image denoising models, we make use of a suitable stochastic gradient method.
Results of several numerical experiments are presented in order to compare both
formulations and the associated augmented Lagrangian methods.
