Halpern-Accelerated Majorized ADMM with Optimal Non-Ergodic Convergence under Degenerate Preconditioning

Abstract

We develop a Halpern-accelerated majorized alternating direction method of multipliers (ADMM) with possibly indefinite proximal terms for linearly constrained convex composite optimization. Majorization simplifies the subproblems but introduces a forward perturbation to the standard degenerate proximal point representation. We reformulate majorized ADMM as a perturbed degenerate proximal point method and characterize the fixed points of the induced mapping as Karush--Kuhn--Tucker (KKT) solutions. Under range compatibility and metric cocoercivity conditions, the mapping is nonexpansive in the seminorm induced by a possibly singular preconditioner. In finite dimensions, a verifiable block-matrix condition permits indefinite proximal regularization while retaining the required metric properties. A relaxed Halpern iteration then yields an $\mathcal O(1/k)$ fixed-point residual bound, sharp in the general nonexpansive setting, and an $\mathcal O(1/k)$ nonergodic KKT residual bound at the intermediate iterates. Numerical experiments illustrate the predicted residual decay and the benefits of majorization and indefinite proximal terms.