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 ℓ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.
Related
- SAFEGUARDED NEURALLY-ACCELERATED PRECONDITIONING (SNAP) FRAMEWORK FOR NONLINEAR OPTIMIZATION
- Weak and Error-Bound Linear Convergence of a Safeguarded Anderson-Accelerated Subgradient Extragradient Method
- Three-dimensional animation compression optimization based on structured processing and adaptive spatiotemporal segmentation algorithm
- A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem via Output Feedback
- Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint
BibTeX
@misc{bian2026safeguarded,
title = {{A Safeguarded Accelerated Proximal ADMM Algorithm for Solving Structured Cardinality Penalized Optimization Problems}},
author = {Wei Bian and Hongyuan Tao and Fan Wu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14559},
eprint = {2610.14559},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14559},
}
RIS
TY - UNPB
TI - A Safeguarded Accelerated Proximal ADMM Algorithm for Solving Structured Cardinality Penalized Optimization Problems
AU - Wei Bian
AU - Hongyuan Tao
AU - Fan Wu
PY - 2026
DA - 2026/10/10
PB - arXiv
DO - 10.48550/arxiv.2610.14559
UR - https://arxiv.org/abs/2610.14559
AB - 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 ℓ_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.
ER -