A Safeguarded Accelerated Proximal ADMM Algorithm for Solving Structured Cardinality Penalized Optimization Problems

Abstract

This paper considers a class of structured cardinality penalized optimization problems with nonsmooth convex loss functions, for which the proximal mapping associated with the structured ${\ell }_0$ penalty is generally unavailable. To overcome this difficulty, we develop a chain of exact reformulations based on variable splitting, exact penalization, and continuous relaxation, and establish rigorous equivalence relationships among these resulting models. In particular, we define a class of strong local minimizers for the original problem and show that these minimizers are equivalent to weak $d$-stationary points of the relaxation problem. Further, we propose a safeguarded accelerated proximal alternating direction method of multipliers (SAP-ADMM). We prove that the sequence generated by SAP-ADMM converges to a weak $d$-stationary point of the relaxation problem. Depending on the parameter settings and algorithmic regime, we establish $O(1/k)$ or $o(1/k)$ convergence rates for both the objective function value gap and the KKT residual. Numerical experiments on signal and image denoising demonstrate the effectiveness of both the proposed models and SAP-ADMM in terms of reconstruction quality and computational efficiency.