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 𝒪(1/k) fixed-point residual bound, sharp in the general nonexpansive setting, and an 𝒪(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.
Related
- cuPDQPx: A GPU-Accelerated Restarted Halpern PDHG for Large-Scale Convex Quadratic Programming
- An Inexact Halpern-accelerated Preconditioned Generalized Proximal Point Algorithm for the Maximal Monotone Inclusion Problem
- SAFEGUARDED NEURALLY-ACCELERATED PRECONDITIONING (SNAP) FRAMEWORK FOR NONLINEAR OPTIMIZATION
- Long-term behaviour of the CAO-system: Optimal polynomial H1-convergence to degenerate equilibria
- The α-Limit Problem: Convergence of a Linear Degenerate Interface Transmission Problem
BibTeX
@misc{zhang2026halpernaccelerated,
title = {{Halpern-Accelerated Majorized ADMM with Optimal Non-Ergodic Convergence under Degenerate Preconditioning}},
author = {Ning Zhang and Benqi Liu and Liwei Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38808},
eprint = {2609.38808},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38808},
}
RIS
TY - UNPB
TI - Halpern-Accelerated Majorized ADMM with Optimal Non-Ergodic Convergence under Degenerate Preconditioning
AU - Ning Zhang
AU - Benqi Liu
AU - Liwei Zhang
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38808
UR - https://arxiv.org/abs/2609.38808
AB - 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 𝒪(1/k) fixed-point residual bound, sharp in the general nonexpansive setting, and an 𝒪(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.
ER -