An Inexact Halpern-accelerated Preconditioned Generalized Proximal Point Algorithm for the Maximal Monotone Inclusion Problem
Abstract
This paper studies an inexact Halpern-accelerated generalized proximal point algorithm with an admissible positive semidefinite preconditioner ℳ for solving maximal monotone inclusion problems. The proposed framework combines Halpern anchoring, resolvent inexactness, and relaxation over the full weight range ρ∈(0,2], thereby covering both under-relaxed and over-relaxed proximal iterations within a unified scheme. We first establish convergence of the inexact resolvent sequence under conditions that allow general anchoring parameters and certain nonsummable tolerances. For anchoring parameters βk=1/(k+r) with r≥2, we then derive explicit bounds on the squared fixed-point residual in the ℳ-seminorm. In particular, if the tolerances satisfy εk=𝒪((k+1)−α) with α>3/2 for 0<ρ<2 and α>2 for ρ=2, these bounds yield an 𝒪(1/k2) convergence rate. The stronger decay condition on the inexactness tolerances at ρ=2 highlights a qualitative distinction between the endpoint and the interior regime in the inexact setting. Finally, we develop inexact accelerated versions of the preconditioned alternating direction method of multipliers (pADMM) and the preconditioned primal--dual hybrid gradient (PDHG) method based on this framework, derive inexactness criteria based on subproblem residuals, and establish a nonergodic 𝒪(1/k) KKT residual rate for their inexact iterates.
Related
- A Safeguarded Accelerated Proximal ADMM Algorithm for Solving Structured Cardinality Penalized Optimization Problems
- Preconditioned Latent Variable Proximal Point Method for Optimal Control Problems with Control Constraints
- A Distributed Accelerated Preconditioned ADMM for Solving Quadratically Regularized Optimal Transport on Bipartite Graphs
- Resilient Decentralized Preconditioned Stochastic Proximal Optimization with Gradient Sketching over Time-Varying Networks
- Proximal-Linearized NEP Method for Composite Optimization with Set-Inclusion and Manifold Constraints
BibTeX
@misc{yang2026inexact,
title = {{An Inexact Halpern-accelerated Preconditioned Generalized Proximal Point Algorithm for the Maximal Monotone Inclusion Problem}},
author = {Lei Yang and Haihang Lan and Di Hou and Ling Liang and Kim-Chuan Toh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05742},
eprint = {2610.05742},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05742},
}
RIS
TY - UNPB
TI - An Inexact Halpern-accelerated Preconditioned Generalized Proximal Point Algorithm for the Maximal Monotone Inclusion Problem
AU - Lei Yang
AU - Haihang Lan
AU - Di Hou
AU - Ling Liang
AU - Kim-Chuan Toh
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.05742
UR - https://arxiv.org/abs/2610.05742
AB - This paper studies an inexact Halpern-accelerated generalized proximal point algorithm with an admissible positive semidefinite preconditioner ℳ for solving maximal monotone inclusion problems. The proposed framework combines Halpern anchoring, resolvent inexactness, and relaxation over the full weight range ρ∈(0,2], thereby covering both under-relaxed and over-relaxed proximal iterations within a unified scheme. We first establish convergence of the inexact resolvent sequence under conditions that allow general anchoring parameters and certain nonsummable tolerances. For anchoring parameters β_k=1/(k+r) with r≥2, we then derive explicit bounds on the squared fixed-point residual in the ℳ-seminorm. In particular, if the tolerances satisfy ε_k=𝒪((k+1)^−α) with α>3/2 for 0<ρ<2 and α>2 for ρ=2, these bounds yield an 𝒪(1/k^2) convergence rate. The stronger decay condition on the inexactness tolerances at ρ=2 highlights a qualitative distinction between the endpoint and the interior regime in the inexact setting. Finally, we develop inexact accelerated versions of the preconditioned alternating direction method of multipliers (pADMM) and the preconditioned primal--dual hybrid gradient (PDHG) method based on this framework, derive inexactness criteria based on subproblem residuals, and establish a nonergodic 𝒪(1/k) KKT residual rate for their inexact iterates.
ER -